题目描述
现在要把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[510],d[510]; int f[510][510]; int ans[510][3]; int main() { scanf("%d%d",&m,&k);memset(f,0x7f,sizeof(f)); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); d[i]=d[i-1]+a[i]; f[1][i]=d[i]; } for(int i=2;i<=k;i++)//k个人，枚举分给的人数。 for(int j=1;j<=m;j++)//枚举i个人共分给j本书 for(int l=1;l<j;l++) if((s=max(f[i-1][l],d[j]-d[l]))<f[i][j]) f[i][j]=s; //这个方案有限制条件 if(k==0) printf("");else if(k==1) printf("1 %d ",m); else { int i=0,j=m,kk=k; for( i=m;i>=0;i--) { if(d[j]-d[i-1]>f[k][m]) { ans[kk][1]=i+1,ans[kk--][2]=j; j=i; } } printf("1 %d ",j); for(int i=2;i<=k;i++) printf("%d %d ",ans[i][1],ans[i][2]); } return 0; } //时间复杂度O(k*m)
第二种二分答案：
本题要求“最优分配方案，使分配给每一个抄写员的页数的最大值最小。” 也就是分配尽量平均，这样，最大值才能尽量小。
但是如果每本书的页数相差太大
int check(int x) { int sum=1,tot=0;//用了sum个人，最后一个人抄了tot页 for(int i=1;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[600]; int ans[60][2]; int check(int x) { int sum=1,tot=0;//用了sum个人，最后一个人抄了tot页 for(int i=1;i<=m;i++) { if((tot+a[i])<=x) tot+=a[i]; else tot=0,sum++,i--; if(sum>m) return sum; } return sum; } int main() { scanf("%d%d",&m,&n); if(n==0) {printf("");return 0;} if(n==1) {printf("1 %d",m);return 0;} int l=1,mid; for(int i=1;i<=m;i++) scanf("%d",&a[i]),all+=a[i];//l=max(l,a[i]) int r=all; while(l<=r) { mid=(l+r)>>1; if(check(mid)>n) l=mid+1; else r=mid-1; } cout<<l; int i=m,tot=0,last=m,t=n; for(i;i>=1;i--) { if((tot+a[i])>l) { ans[t][0]=i+1,ans[t][1]=last;t--; last=i;tot=a[i]; }else tot+=a[i]; } /* printf("1 %d ",last); for( i=2;i<=n;i++) printf("%d %d ",ans[i][0],ans[i][1]); */ return 0; }