[VijosP1639]机密文件 题解

题目大意：

　　m个人抄n份资料，资料有编号，每人抄连续的几份资料，每份资料页数不一定相等，每个人抄的速度相同，求使得总时间最少的方案（总时间相同，越前面的人抄的越少）

思路：

　　假设每人一天抄一页，二分天数，倒着安排资料即可。

代码：

#include<cstdio>
int n,m,l,r,i,p,a[1001],ans[1001];

bool check(int x)
{
    int i=n,t=0,cnt=0;
    for (;i>=0;--i)
    {
        t=t+a[i];
        if (t>x)
        {
            t=0; ++i;
            if (++cnt>m) return 0;
        }
    }
    if (t) t=1;
    return t+cnt<=m;
}

int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&a[i]),r=r+a[i];
    for (l=0;l<r;)
    {
        int mid=l+r>>1;
        if (check(mid)) r=mid; else l=mid+1;
    }
    r=0,p=m;
    for (i=n;i;--i)
    {
        r=r+a[i];
        if (r>l)
        {
            r=0;
            ans[p--]=++i;
        }
    }
    printf("1 %d
",ans[p+1]-1);
    for (i=p+1;i<m;i++) printf("%d %d
",ans[i],ans[i+1]-1);
    printf("%d %d",ans[m],n);
    return 0;
}