本文主要是介绍Codeforces Round #307 (Div. 2)-C. GukiZ hates Boxes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C. GukiZ hates Boxes
题目链接：http://codeforces.com/problemset/problem/551/C
Description
Professor GukiZ is concerned about making his way to school, because massive piles of boxes are blocking his way.
In total there are n piles of boxes, arranged in a line, from left to right, i-th pile (1 ≤ i ≤ n) containing ai boxes. Luckily, m students are willing to help GukiZ by removing all the boxes from his way. Students are working simultaneously. At time 0, all students are located left of the first pile. It takes one second for every student to move from this position to the first pile, and after that, every student must start performing sequence of two possible operations, each taking one second to complete. Possible operations are:
If i ≠ n, move from pile i to pile i + 1;
If pile located at the position of student is not empty, remove one box from it.
GukiZ's students aren't smart at all, so they need you to tell them how to remove boxes before professor comes (he is very impatient man, and doesn't want to wait). They ask you to calculate minumum time t in seconds for which they can remove all the boxes from GukiZ's way. Note that students can be positioned in any manner after t seconds, but all the boxes must be removed.
In total there are n piles of boxes, arranged in a line, from left to right, i-th pile (1 ≤ i ≤ n) containing ai boxes. Luckily, m students are willing to help GukiZ by removing all the boxes from his way. Students are working simultaneously. At time 0, all students are located left of the first pile. It takes one second for every student to move from this position to the first pile, and after that, every student must start performing sequence of two possible operations, each taking one second to complete. Possible operations are:
If i ≠ n, move from pile i to pile i + 1;
If pile located at the position of student is not empty, remove one box from it.
GukiZ's students aren't smart at all, so they need you to tell them how to remove boxes before professor comes (he is very impatient man, and doesn't want to wait). They ask you to calculate minumum time t in seconds for which they can remove all the boxes from GukiZ's way. Note that students can be positioned in any manner after t seconds, but all the boxes must be removed.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 105), the number of piles of boxes and the number of GukiZ's students.
The second line contains n integers a1, a2, ... an (0 ≤ ai ≤ 109) where ai represents the number of boxes on i-th pile. It's guaranteed that at least one pile of is non-empty.
The second line contains n integers a1, a2, ... an (0 ≤ ai ≤ 109) where ai represents the number of boxes on i-th pile. It's guaranteed that at least one pile of is non-empty.
Output
In a single line, print one number, minimum time needed to remove all the boxes in seconds.
Sample Input
2 1
1 1
Sample Output
4
题意：有N堆物品，每堆物品数量为a[i]，有M个小学生帮忙搬东西，每天可以搬1个物品或者移动一格，小学生起始点在0点，问最少天数是多少。
题解：二分需要的天数，然后贪心求每个人能搬走的最多物品，看当前天数能不能将所有的物品搬走。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100007;
int n,m;
long long sum,a[maxn],b[maxn];
int check(long long x)
{for(int i=1;i<=n;i++)b[i]=a[i];long long step = 0;int k = n;for(int i=1;i<=m;i++){while(b[k]==0&&k>=1){k--;}step = k;if(step>x)continue;while(x>=(b[k]+step)&&k>=1){step+=b[k];b[k]=0;k--;}if(k==0)return 1;b[k]-=(x-step);}return 0;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}sum+=n;long long l = 0;long long r =sum;long long ans;while(l<r){long long mid = (l+r)/2;if(check(mid))r = mid;else l = mid+1;ans = r;}cout<<ans<<endl;return 0;
}这篇关于Codeforces Round #307 (Div. 2)-C. GukiZ hates Boxes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
