本文主要是介绍Codeforces Round #307 (Div. 2)C. GukiZ hates Boxes(二分+贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/551/problem/C
题目大意：有n堆箱子，每堆箱子有a[i]个箱子，一共n个人，每个人每秒可以选择向右走一步或者拿一个箱子，问最少花多少时间拿掉所有箱子。
题目思路：二分时间，假设每个人都拥有x的时间，那么就一个个的去，每个人都尽全力去拿箱子，当sum+i>=x的时候就说明超出了一个人的能力范围，那就需要再派一个人过来，tnt--。最后如果没人的话，要看sum是否为0，如果>0的话就说明还不够消掉所有箱子。有一个坑点就是要找到最后一个非0的点，否则他会跑到最后一个，但实际上是没有必要的，因为后面没箱子可以取了，没必要花时间走到那里。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
ll n,m,a[MAXN],p;
bool check(ll x){ll tnt=m,sum=0;rep(i,1,p){sum+=a[i];while(sum+i>=x){sum-=x-i;tnt--;if(tnt<0)return 0;}}if(!tnt&&sum>0)return 0;return 1;
}
int main()
{while(~scanf("%I64d%I64d",&n,&m)){rep(i,1,n)scanf("%I64d",&a[i]);per(i,n,1)if(a[i]){p=i;break;}ll l=0,r=1e15,ans=-1;while(l<=r){ll mid=(l+r)>>1;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}cout<<ans<<endl;}return 0;
}
这篇关于Codeforces Round #307 (Div. 2)C. GukiZ hates Boxes(二分+贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
