题目传送门


【题意】m个人要去移动n堆盒子  每堆上有若干个盒子  每个人只能进行两种操作 从一个位置走到下一个位置  如果这个位置上的盒子个数不为0  那么就要把这个位置上的盒子移掉  每种操作需要一秒

求这m个人 把盒子全都清掉所花的最少时间.


【解题思路】二分所需要的时间 对每个人进行贪心  从最远的地方开始  让每个人在时间范围内移动更多数目的盒子堆数m个人要去移动n堆盒子  每堆上有若干个盒子  每个人只能进行两种操作 从一个位置走到下一个位置  如果这个位置上的盒子个数不为0  那么就要把这个位置上的盒子移掉  每种操作需要一秒,求这m个人 把盒子全都清掉所花的最少时间

 

【具体做法】二分所需要的时间 对每个人进行贪心  从最远的地方开始  让每个人在时间范围内移动更多数目的盒子堆数


 
//Created Author :just_sort
//Created Time   :2016/1/23 14:42
//Created File   :GukiZ hates Boxes.
#include <cstdio>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 100010;

int n,m,tot;
ll a[maxn];
int check(ll x)//在x的时间限制内，是否能搬完所有的box.
{
    int i,cnt=m;
    ll s=0;
    for(i=1;i<=tot;i++)
    {
        s+=a[i];
        while(s+i>=x)//移动箱子加上走的路程超过了x.
        {
            s-=x-i;//对于当前已经走的路程，一个人有x-i的时间来搬箱子，那么每增加一个人，搬箱子的时间减少x-i.
            cnt--;
            if(cnt<0)return 0;
        }
    }
    if(cnt==0)return s<=0;
    return 1;
}
int main()
{
    ll l,r,ans,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        if(a[i])tot=i;//记录最右边的不为0的数的位置.
    }
    l=tot,r=sum+tot;
//    cout<<l<<"   "<<r<<endl;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    printf("%I64d\n",ans);
    return 0;
}