Garbage Disposal(模拟垃圾装垃圾口袋)

Garbage Disposal

Description

Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next n

days Vasya knows ai — number of units of garbage he will produce on the i-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to k

units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given n

days. No garbage should be left after the n

-th day.

Input

The first line of the input contains two integers n

and k (1≤n≤2⋅105,1≤k≤109) — number of days to consider and bag's capacity. The second line contains n space separated integers ai (0≤ai≤109) — the number of units of garbage produced on the i

-th day.

Output

Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the n

-th day. In a day it is allowed to compose and drop multiple bags.

Sample Input

Input

3 2
3 2 1

Output

Input

5 1
1000000000 1000000000 1000000000 1000000000 1000000000

Output

5000000000

Input

3 2
1 0 1

Output

Input

4 4
2 8 4 1

Output

4
题意：
有n天，第i天有a[i]个垃圾，每天的垃圾最多能留到第二天扔，每个垃圾口袋最多装k个垃圾，问，最少用多少个垃圾口袋能把所有的垃圾装完。
思路：
把每天的垃圾数分两种，一种是刚好能用垃圾口袋装下的;一种是还剩余的垃圾，这个时候，把剩余的垃圾留到第二天去处理，将第二天的垃圾数减掉（k-剩余的），让第一天剩余的垃圾和第二天里的垃圾凑成一个垃圾口袋
如果，第二天的垃圾数减去第一天需要的后小于0，这个时候就让第二天的垃圾数等于0。然后输出垃圾口袋数就好
注意ans要开long long

 1 #include<algorithm>

 2 #include<cstdio>

 3 #include<iostream>

 4 using namespace std;

 5 int main(){

 6     int n,k;

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

 8         int a[200005];

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

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

11         long long ans=0,t=0;

12         for(int i=1;i<=n;i++) {

13             ans+=a[i]/k;//当天刚好能装袋的垃圾

14             t=a[i]%k;//剩余没能当天装袋的垃圾

15             if(t){//如果剩余的垃圾>0

16

17                 a[i+1]-=k-t;//将第二天的垃圾数减去第一天剩余装袋的垃圾所需要的垃圾

18                 if(a[i+1]<0)//如果相见之后垃圾数<0

19                     a[i+1]=0;//让垃圾数=0

20                 ans++;//垃圾口袋数++

21             }

22         }

23         printf("%lld\n",ans);

24     }

25     return 0;

26 }

巴特西

Garbage Disposal(模拟垃圾装垃圾口袋)

最新文章

热门文章