题目描述
现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
输入输出格式
输入格式：
第一行两个整数m，k；（k≤m≤500）
第二行m个整数，第i个整数表示第i本书的页数。
输出格式：
共k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
输入输出样例
输入样例#1：
9 3
1 2 3 4 5 6 7 8 9
输出样例#1：
1 5
6 7
8 9
分析：两种做法。
一dp做法：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<math.h>
using namespace std;
int k,m,s;
int a[],d[];
int f[][];
int ans[][];
int main()
{
scanf("%d%d",&m,&k);memset(f,0x7f,sizeof(f));
for(int i=;i<=m;i++)
{
scanf("%d",&a[i]);
d[i]=d[i-]+a[i];
f[][i]=d[i];
}
for(int i=;i<=k;i++)//k个人，枚举分给的人数。
for(int j=;j<=m;j++)//枚举i个人共分给j本书
for(int l=;l<j;l++)
if((s=max(f[i-][l],d[j]-d[l]))<f[i][j])
f[i][j]=s;
//这个方案有限制条件
if(k==) printf("");else
if(k==) printf("1 %d\n",m);
else
{
int i=,j=m,kk=k;
for( i=m;i>=;i--)
{
if(d[j]-d[i-]>f[k][m])
{
ans[kk][]=i+,ans[kk--][]=j;
j=i;
}
}
printf("1 %d\n",j);
for(int i=;i<=k;i++)
printf("%d %d\n",ans[i][],ans[i][]);
} return ;
} //时间复杂度O(k*m)
第二种二分答案：
本题要求“最优分配方案，使分配给每一个抄写员的页数的最大值最小。” 也就是分配尽量平均，这样，最大值才能尽量小。
但是如果每本书的页数相差太大
int check(int x)
{
int sum=,tot=;//用了sum个人，最后一个人抄了tot页
for(int i=;i<=m;i++)
{
if((tot+a[i])<=x)
tot+=a[i];
else
tot=a[i],sum++; //这个代码的话，就默认了下一个人肯定能抄这本书。也就是说默认了a[i]<=x，所以需要把可行最小值l=max(页数a[i]).
}
return sum;
}
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<math.h>
using namespace std;
int m,n,all;
int a[];
int ans[][];
int check(int x)
{
int sum=,tot=;//用了sum个人，最后一个人抄了tot页
for(int i=;i<=m;i++)
{
if((tot+a[i])<=x)
tot+=a[i];
else
tot=,sum++,i--;
if(sum>m) return sum;
}
return sum;
}
int main()
{
scanf("%d%d",&m,&n);
if(n==) {printf("");return ;}
if(n==) {printf("1 %d",m);return ;}
int l=,mid;
for(int i=;i<=m;i++)
scanf("%d",&a[i]),all+=a[i];//l=max(l,a[i])
int r=all;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid)>n)
l=mid+;
else r=mid-;
}
cout<<l;
int i=m,tot=,last=m,t=n;
for(i;i>=;i--)
{
if((tot+a[i])>l)
{
ans[t][]=i+,ans[t][]=last;t--;
last=i;tot=a[i];
}else
tot+=a[i];
}
/*
printf("1 %d\n",last);
for( i=2;i<=n;i++)
printf("%d %d\n",ans[i][0],ans[i][1]);
*/
return ;
}