为什么要把这两道题放到一起写呢？就是因为这两道题很像很像只有输不输出方案的区别~
不信把两道题目一起放出来！！
时间限制: 1 Sec 内存限制: 64 MB
把一个包含n个正整数的序列划分为m个连续的子序列(子序列不能重叠)。设第i个序列的各数之和为S(i),你的任务是让所有S(i)的极大值尽量小。例如序列1 2 3 2 5 4划分为3个序列的最优方案为123|25|4，其中S(1),S(2),S(3)分别为6，7，4，极大值为7；如果划分为12|32|54，则极大值为9，不如刚才的好。N<1000000，所有数的和不超过10^9.
输入数据： 第一行：两个正整数n，m。 第二行：n个正整数，表示该序列。
输出数据： 最小的极大序列和
Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)
6 3 1 2 3 2 5 4
提示： 序列1 2 3 2 5 4划分为3个序列的最优方案为123|25|4，其中S(1),S(2),S(3)分别为6，7，4，极大值为7。其他的方案得到的极大值都大于7.所以输出7.
时间限制: 1 Sec 内存限制: 64 MB
现在要把m本有顺序的书分给k给人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。
第一行两个整数m，k；（k≤m≤500） 第二行m个整数，第i个整数表示第i本书的页数。
共k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
Copy (如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)
9 3 1 2 3 4 5 6 7 8 9
这就是hin典型的二分答案的题~2~1嘛~
BUT！！！！！what is erfen？？
所谓二分，就是把一个区间对折对折再对折~~
这样做的前提，就是你可以知道对折后该走哪一边~~
算了直接给你们领略一下代码~
#include<cstdio> int n,m,a[1000005],s; int sc(int bg,int ed) { if(bg==ed) return bg; int mid=(bg+ed)/2; int i,j=1,k=0,f=0; for(i=n;i>=1;i--) { if(a[i]>mid) { f=1;break; } if(k+a[i]>mid) { j++; k=0; } if(j>m) { f=1;break; } k+=a[i]; } if(f) return sc(mid+1,ed); else return sc(bg,mid); } int main() { int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); s+=a[i]; } printf("%d",sc(0,s)); } /************************************************************** Problem: 1544 User: C20172037dza Language: C++ Result: 正确 Time:290 ms Memory:4936 kb ****************************************************************/
#include<cstdio> #include<cstring> int n,m,a[505],s,p[505],q[505],p1[505],q1[505]; void sc(int bg,int ed) { int mid=(bg+ed)/2; int i,j,k=0; q1[1]=n; for(i=n,j=1;i>=1&&j<=m&&a[i]<=mid;i--) { if(k+a[i]>mid) { p1[j]=i+1; q1[j+1]=i; j++; k=0; } k+=a[i]; } p1[m]=1; if(bg==ed) { memcpy(p,p1,sizeof(p1)); memcpy(q,q1,sizeof(q1)); return; } if(j>m||a[i]>mid) sc(mid+1,ed); else sc(bg,mid); } int main() { int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); s+=a[i]; } sc(0,s); for(i=m;i>0;i--) printf("%d %d\n",p[i],q[i]); } /************************************************************** Problem: 1233 User: C20172037dza Language: C++ Result: 正确 Time:0 ms Memory:1040 kb ****************************************************************/
你们会发现，我只把输出方案的部分添加了，别的动了很少~~
话说我做1544的时候没有判断
if(a[i]>mid) { f=1;break; }if(a[i]>mid) { f=1;break; }
于是hin华丽地WA了= =真t是m愉d快啊..
我也是在单步调试的时候发现的这个问题..
简直了..pen pineapple apple pen
果然还是要多测几组数据，不能过个样例就屁颠屁颠去提交= =
然后1233就是说如果多解就让前面的人少抄就是让后面的多抄嘛~~
然后二分能不能取mid要慎重考虑！！慎重考虑！！慎重考虑！！
剩下的等我AC再说...
