B. Vanya and Food Processor【转】
B. Vanya and Food Processortime limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed hand the processor smashes k centimeters of potato each second. If there are less than k centimeters remaining, than during this second processor smashes all the remaining potato.
Vanya has n pieces of potato, the height of the i-th piece is equal to ai. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number n. Formally, each second the following happens:
- If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.
- Processor smashes k centimeters of potato (or just everything that is inside).
Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.
InputThe first line of the input contains integers n, h and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.
The second line contains n integers ai (1 ≤ ai ≤ h) — the heights of the pieces.
OutputPrint a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.
Examplesinput5 6 3
5 4 3 2 1output5input5 6 3
5 5 5 5 5output10input5 6 3
1 2 1 1 1output2NoteConsider the first sample.
- First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2 remaining inside.
- Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3 remaining.
- Vanya puts the piece of height 3 inside and again there are only 3 centimeters remaining at the end of this second.
- Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3.
- During this second processor finally smashes all the remaining potato and the process finishes.
In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10 seconds.
In the third sample, Vanya simply puts all the potato inside the processor and waits 2 seconds.
题解代码:
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x,cur_h,k;
int main()
{
cin >> n >> h >> k;
ans = ;
cur_h = ;
for (i = ; i < n; i++)
{
scanf("%I64d", &x);
if (cur_h + x <= h)
cur_h += x;
else
ans++, cur_h = x;
ans += cur_h/k;
cur_h %= k;
}
ans += cur_h/k;
cur_h %= k;
ans += (cur_h>);
cout << ans << endl;
return ;
}
最新文章
- win7搭建双系统ubuntu
- SublimeText2 快捷键一览表
- JAVA 重复提交
- 简易线程池Thread Pool
- 用xutils3.0进行下载
- xargs命令
- createElement创建标签及appendChild添加到元素的后面
- TDD(测试驱动开发)培训录(转)
- Linux LVS Nginx HAProxy 优缺点
- Nightmare
- Spring+Mybatis+jQuery.Pagination.js异步分页及JsonConfig的使用
- Cocos2d-x 开发手记
- 【Unity--Apwork框架】AOP编程--拦截,用于缓存和异常处理(Unity框架的拦截注入-Interception)
- 在iis中mantisbt配置过程
- bzoj3043
- Struts2 处理表单重复提交
- for 的多重循环--java
- 分珠(dfs+并查集)
- video.js支持m3u8格式直播
- 强化学习(八)价值函数的近似表示与Deep Q-Learning