问题描述：
把一个包含n个正整数的序列划分成m个连续的子序列。设第i个序列的各数之和为S(i)，求所有S(i)的最大值最小是多少？
例如序列1 2 3 2 5 4划分为3个子序列的最优方案为 1 2 3 | 2 5 | 4，其中S(1),S(2),S(3)分别为6，7，4，那么最大值为7；
如果划分为 1 2 | 3 2 | 5 4，则最大值为9，不是最小。
[2018.3.18补充]
就是不断去尝试那个最大值ｍ, 如果以ｍ为最大值看看是不是能划分ｍ个子序列，如果可以的话，那么就可以往小了再试试，如果根本不能划分ｍ个子序列,会剩下一些数，那么最大值就要变大一点
参考博客：http://blog.csdn.net/nanjunxiao/article/details/8145971
这个答案就是介于这六个数最大值和总和之间的一个，然后就二分查找，判断是否mid可以，
判断mid就是一个循环看看是否最多插m - 1（少没事，多就不行）个空，是每一段和少于等于mid。
题目1502：最大值最小化http://ac.jobdu.com/problem.php?pid=1502
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：540
解决：201
- 题目描述：
-
在印刷术发明之前，复制一本书是一个很困难的工作，工作量很大，而且需要大家的积极配合来抄写一本书，团队合作能力很重要。
当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书，编号为1,2,3...m, 每本书有1<=x<=100000页， 把这些书分配给k个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，你的任务就是找到一个最佳的分配方案，使得所有书被抄完所用的时间最少。
- 输入：
-
输入可能包含多个测试样例。
第一行仅包含正整数 n，表示测试案例的个数。
对于每个测试案例，每个案例由两行组成，在第一行中，有两个整数m和 k， 1<=k<=m<=500。 在第二行中，有m个整数用空格分隔。 所有这些值都为正且小于100000。
- 输出：
-
对应每个测试案例，
输出一行数字，代表最佳的分配方案全部抄写完毕所需要的时间。
- 样例输入：
-
2 9 3 100 200 300 400 500 600 700 800 900 5 4 100 100 100 100 100
- 样例输出：
-
1700 200
- 来源：
- 网易有道2013年校园招聘面试一面试题
-
View Code1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 const int MAX = 500 + 10; 7 int m,k; 8 int a[MAX]; 9 bool is_ok(int maxn) 10 { 11 bool ok = true; 12 int s = 0,cnt = 0; 13 for(int i = 1; i <= m; i++) 14 { 15 if(a[i] > maxn) 16 { 17 ok = false; 18 break; 19 } 20 if(s + a[i] > maxn) 21 { 22 cnt++; 23 s = a[i]; 24 if(cnt > k - 1) 25 { 26 ok = false; 27 break; 28 } 29 } 30 else 31 { 32 s += a[i]; 33 } 34 } 35 return ok; 36 } 37 int solve(int x, int y) 38 { 39 while(x <= y) 40 { 41 int mid = (x + y) / 2; 42 if( is_ok(mid) ) 43 y = mid - 1; 44 else 45 x = mid + 1; 46 } 47 return x; 48 } 49 int main() 50 { 51 int t; 52 scanf("%d", &t); 53 while(t--) 54 { 55 int maxn = 0,sum = 0; 56 scanf("%d%d", &m, &k); 57 for(int i = 1; i <= m; i++) 58 { 59 scanf("%d", &a[i]); 60 if(maxn < a[i]) 61 maxn = a[i]; 62 sum += a[i]; 63 } 64 printf("%d ", solve(maxn, sum)); 65 } 66 return 0; 67 }
