题目大意：
要抄N本书，编号为1,2,3...N, 每本书有1<=x<=10000000页， 把这些书分配给K个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，求所有书抄完所用的最少时间的分配方案。
题目中的要求是去求划分的子序列的最大值尽量小，最大值最小化，如果从划分的角度看，无法获得好的思路，我们可以从值得角度考虑，所要求的最小的最大值必定是从[amax,sum(总和)]中取得的，那么我们可以二分法的方式猜测一个数字，看它是否满足要求，如果满足要求，我们可以继续缩小范围。
实现的另一个关键是划分，题目说如果有多解的话，前面的要求尽量小，那么我们的划分必然是从右往左划分，我们可以先做判断，如果都要求划分的值尽量达到最大值，它的划分个数小于要求的划分数，它就是满足条件的，因为我们可以将某一个划分组的序列拆解下来（子序列在拆解），它也一定是满足条件的，因为小于最大值肯定是对的，在贪心的过程中，一旦还需要划分组数正好等还剩下的整数数量的话，直接将每一个数作为一个划分组即可。
下面一篇博文将重点介绍一下二分查找的有关细节。
1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 505 4 using namespace std; 5 int num[MAXN]; 6 int mark[MAXN]; 7 int n,m,k; 8 long long low=-1,high=0; 9 void init(){ 10 low = -1; 11 high = 0; 12 memset(mark,0,sizeof(mark)); 13 } 14 bool solve(long long mid){ 15 //进行判断是否可以划分为某个最小最大值的序列 16 long long sum=0; 17 int t=1; 18 for(int i = m-1;i >=0 ; i--){ 19 if(sum + num[i] > mid){ 20 sum = num[i]; 21 t++; 22 if(t > k) 23 return false; 24 } 25 else 26 sum += num[i]; 27 } 28 return true; 29 } 30 void print(long long s){ 31 long long sum = 0; 32 int t = 1,i,j; 33 for(i = m-1;i >=0 ; i--){ 34 if(sum + num[i] > s){ 35 //贪心的关键，尽量值靠近最大值 36 sum = num[i]; 37 mark[i] = 1; 38 t++; 39 } 40 else{ 41 sum +=num[i]; 42 } 43 if(k - t == i + 1){ 44 //贪心的关键 45 //如果剩下来的值的数量正好等于要划分的组数那么每一个数为一组 46 for(j = 0 ;j <= i; j++){ 47 mark[j] = 1; 48 } 49 break; 50 } 51 } 52 for(i = 0 ;i < m-1 ; i++){ 53 printf("%d ",num[i]); 54 if(mark[i]==1){ 55 printf("/ "); 56 } 57 } 58 printf("%d ",num[m-1]); 59 } 60 int main(){ 61 long long left,right,mid; 62 scanf("%d",&n); 63 while(n--){ 64 init(); 65 scanf("%d%d",&m,&k); 66 for(int i = 0 ; i < m ;i++){ 67 scanf("%d",&num[i]); 68 if(low < num[i]) 69 low = num[i]; 70 high+=num[i]; 71 } 72 left = low; 73 right = high; 74 while(left <= right){ 75 memset(mark,0,sizeof(mark)); 76 mid = left + (right - left)/2; 77 if(solve(mid)){ 78 right = mid - 1; 79 } 80 else 81 { 82 left = mid + 1; 83 } 84 } 85 print(left); 86 } 87 return 0; 88 }