CodeForces 382B 数学推导

这个题目题意简单，但是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=;

        if (c>a)

        ans=ceil(((c-a)*x-b)*1.0/(1.0*(w-x)))+c-a;

        printf("%I64d\n",ans);

    }

    return ;

}

巴特西

CodeForces 382B 数学推导

最新文章

热门文章