D. Garbage Disposal
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 nn days Vasya knows aiai — number of units of garbage he will produce on the ii-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 kk 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 nn days. No garbage should be left after the nn-th day.
Input
The first line of the input contains two integers nn and kk (1≤n≤2⋅105,1≤k≤1091≤n≤2⋅105,1≤k≤109) — number of days to consider and bag's capacity. The second line contains nn space separated integers aiai (0≤ai≤1090≤ai≤109) — the number of units of garbage produced on the ii-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 nn-th day. In a day it is allowed to compose and drop multiple bags.
Examples
input
Copy
代码语言：javascript复制3 2
3 2 1output
Copy
代码语言：javascript复制3input
Copy
代码语言：javascript复制5 1
1000000000 1000000000 1000000000 1000000000 1000000000output
Copy
代码语言：javascript复制5000000000input
Copy
代码语言：javascript复制3 2
1 0 1output
Copy
代码语言：javascript复制2input
Copy
代码语言：javascript复制4 4
2 8 4 1output
Copy
代码语言：javascript复制4
题意：倒垃圾，a[i]表示垃圾数目，必须每一个垃圾必须要用容量为k的垃圾袋装，i表示第i天，当天的垃圾最多只能留到第二天，求最少花费的垃圾袋数思路：贪心，对于每一个垃圾袋而言，要尽量的装满，当天的垃圾能装满一个袋子就马上装好，剩下a[i]%k个垃圾可以第二天和第二天的垃圾一起装
代码语言：javascript复制// luogu-judger-enable-o2
#include<bits/stdc .h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 300005
const double eps = 1e-6;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) (s << 3) (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 48);
}
ll n,k,a[maxn];
int main()
{
cin>>n>>k;
for(rg i=1;i<=n;i )a[i]=read();
ll sum=0,temp=inf;
for(rg i=1;i<=n;i )
{
if(temp<=k&&temp)
{
sum ;
a[i]-=k-temp;
if(a[i]<0)a[i]=0;
}
if(a[i]>=0)
{
sum =a[i]/k;
temp=a[i]%k;
}
//cout<<temp<<" "<<sum<<" "<<a[i]<<endl;
}
cout<<sum (temp!=0)<<endl;
return 0;
}
