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 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.
Sample Input
Input
3 2 3 2 1
Output
3
Input
5 1 1000000000 1000000000 1000000000 1000000000 1000000000
Output
5000000000
Input
3 2 1 0 1
Output
2
Input
4 4 2 8 4 1
Output
4
题解:
简单题,但是做错了。。。。每天要解决今天和昨天的垃圾,今天的可以留给明天,最后一天必须全部干完,一次解决k,问需要多少次?
代码如下:
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <ctime>
#define maxn 200007
#define N 100005
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define eps 0.000000001
#define read(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define Debug(x) cout<<x<<" "<<endl
using namespace std;
typedef long long ll;
int a[200007],c[200007];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
ll sum=0;
sum+=a[0]/k;
int s=a[0]%k;
for(int i=1;i<n;i++)
{
if(s+a[i]>=k)
{
sum+=(s+a[i])/k;
s=(s+a[i])%k;
}
else if(s==0&&a[i]==0)
continue;
else if(s==0&&a[i]<k)
s=a[i];
else
{
sum++;
s=0;
}
//cout<<sum<<" "<<s<<endl;
}
if(s>0)
sum++;
cout<<sum<<endl;
return 0;
}
上一篇: 商山四皓是什么人?为什么刘邦见到他们就放弃了废太子的想法?
下一篇: 关于 JS this
推荐阅读
-
全面了解JavaScirpt 的垃圾(garbage collection)回收机制
-
[JVM 相关] Java 新型垃圾回收器(Garbage First,G1)
-
JAVA垃圾回收GARBAGE COLLECTION(二、垃圾收集器)
-
[JVM 相关] Java 新型垃圾回收器(Garbage First,G1)
-
netty使用中的LEAK: ByteBuf.release() was not called before it‘s garbage-collected
-
python面试题之简要描述Python的垃圾回收机制(garbage collection)
-
全面了解JavaScirpt 的垃圾(garbage collection)回收机制
-
浅谈PHP5中垃圾回收算法(Garbage Collection)的演化
-
使用Chrome开发者工具分析JavaScript garbage collector(垃圾回收器) SAPC4CCloudCDS viewCloudFoundry
-
使用Chrome开发者工具分析JavaScript garbage collector(垃圾回收器)的实现原理 chromeSAPSAP云平台SAP Cloud PlatformSAP成都研究院