Codeforces Round #355 (Div. 2)-B. Vanya and Food Processor，纯考思路~~

B. Vanya and Food Processor

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

->
Link <-

cf上的题果然很靠思路，这让我想起了学长说的那句话：每A完CF上的一套题都有不同的收获。

这道题题意倒是不难理解：有一台机器，每次只能处理K cm的土豆，这台机器最多能放下hcm的土豆，如果剩下的土豆长度不足K,则1 s将其处理完；问给定顺序的n个土豆最少要用多少时间才能处理完；

看样例就可以懂这道题的题意了，那么怎么做呢？我们发现无论土豆怎么放，每秒最多也只能处理K cm长的土豆，而条件限制是机器里能容纳的最大长度是h，然后就可以用一个贪心策略来解决；我们知道土豆的顺序是固定的，所以我们可以先放第一个，如果长度不足h则再判断下一个是否能放下，如果还能则继续判断下下个是否能够放下，如果当放完前一个，而放后一个总长度就会大于h时，显然不合题意，所以我们得先处理完机器里面的，每处理1 s机器里的总长度就减k，所以处理完需要sum/k的时间，这时机器里面的就可能有剩余了，然后再判断刚刚那个没有放进去的土豆能否放得下，如果可以则继续放，如果这个土豆都不能放下，则刚刚机器里剩余的即使小于k还是需要1
s来处理完，这时机器里的总长度就为0了，然后就相当于回到了初始状态；

这道题我觉得很考思维的地方就在于我们现实中往机器里放东西是要时间的，而这里当机器处理完放东西进去是不用时间的，只需要判断处理的时间与放东西的状态是否符合题意，往往就是受现实生活的影响而影响了自己的思维；

#include<bits/stdc++.h>

using namespace std;

const int N=100000+10;

long long a[N];//注意题目数据范围；

int main()

{

    int n,k,h,i;

    while(~scanf("%d%d%d",&n,&h,&k))

    {

        long long x=0;

        long long sum=0;

        for(i=1; i<=n; i++)

        {

            scanf("%I64d",&a[i]);

            if(a[i]>h) continue;//实际上题目已经说明了，所以可以省略；

            if(sum+a[i]>h)//如果当前的土豆不能放进去，所以我们要先处理完机器里面的；

            {

                x+=sum/k;

                 sum%=k;

                if(sum+a[i]>h)//如果还有剩余，而当前要放进去的土豆又不能放进去则必须先处理完机器里面的；

                {

                    sum=0;

                    x++;

                }

            }

            sum+=a[i];//将当前待放得土豆放进去；

        }

        x+=sum/k;

        if(sum%k)

            x++;

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

    }

    return 0;

}

巴特西

Codeforces Round #355 (Div. 2)-B. Vanya and Food Processor，纯考思路~~

最新文章

热门文章