这个题目题意简单,但是TLE得哭哭的。。。
输入 a b w x c五个数,最终要使得c<=a, 每一秒可以进行一个操作,如果b>=x,则 b=b-x,同时 c--;如果b<x,则a--,c--,b=w-(x-b),最终求满足c<=a时候已经走过的秒数。
我们可以看到,x ,w是里面的定量,b相当于一个控制开关,它的量决定了要进行哪种操作,c在任意一秒都会递减,而a只会在b<x的时候递减,换句话说,b>=x的时候,c和a才差距减少1,我一开始的优化是,分别对于两个条件,第一个,直接求出b小于x之前总共能撑几秒,这样直接把c减少就行,。。。对第二个条件,稍微推导一下发现,每一秒b是递增了w-x(题目条件说了w>x),因此也可以直接求出b在满足该条件时能撑几秒,直接加到结果里。。。但是这样的优化显然不够,结果任然是TLE,所以需要更强力的推导
于是前面已经说到,c和a只有在第一个条件的时候才会距离缩短1,也就是说从头到尾,第一个条件总共会占用 c-a秒,这个很好理解。。。另外,我们设第二个条件总共发生了k秒,
则会有这样的不等式出来 b-(c-a)*x+(w-x)*k+x>=x,这就表示,因为最后一秒一定是进行b-x操作,因此,整个左边式子除去最后一个+x,就是b最后的值,而这个值只有一个限定条件,即 再加上x之后 就回到了最后一秒发生前的状态 它必定b>=x 所以有此式
这个式子化简一下 就能求出关于k的不等式,取k的最小整数再+c-a 即为最后答案
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #define ll long long using namespace std; ll a,b,w,x,c; int main() { while (scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&w,&x,&c)!=EOF) { ll ans=0; if (c>a) ans=ceil(((c-a)*x-b)*1.0/(1.0*(w-x)))+c-a; printf("%I64d\n",ans); } return 0; }