九度：/problem.php?pid=1502题目描述：
在印刷术发明之前，复制一本书是一个很困难的工作，工作量很大，而且需要大家的积极配合来抄写一本书，团队合作能力很重要。
当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书，编号为1,2,3...m, 每本书有1<=x<=100000页， 把这些书分配给k个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，你的任务就是找到一个最佳的分配方案，使得所有书被抄完所用的时间最少。
输入：
输入可能包含多个测试样例。
第一行仅包含正整数 n，表示测试案例的个数。
对于每个测试案例，每个案例由两行组成，在第一行中，有两个整数m和 k， 1<=k<=m<=500。 在第二行中，有m个整数用空格分隔。 所有这些值都为正且小于100000。
输出：
对应每个测试案例，
输出一行数字，代表最佳的分配方案全部抄写完毕所需要的时间。
样例输入：
29 3100 200 300 400 500 600 700 800 9005 4100 100 100 100 100
样例输出：
1700200
这个题目的解法比较有趣。我们先定义一个人抄的页数的总和为工作量。
首先，一个合理的答案ans应该满足下面的条件：
1、 每一份工作量不大于ans，且其中一份或者几份的工作量等于ans。
2、 分成的份数不大于k。
但是满足上述条件的ans未必是最优解。例如ans=所有页数的总和时，也一样满足上述两个条件。仔细想想，我们的目的是使得书籍正好可以被所有人抄完，且尽量不要有人闲着，换言之，我们应该找出来一个值t，它应该满足第三个条件：t如果被减1，条件1或者2会被破坏。可以用反证法证明，t是最优解。
由于这个题目有个特殊性，就是每个人只能抄连续的几本书，故我们可以二分得到答案。取所有书籍页数最多的为下界base，所有书籍的页数和为上界top，每次验证mid是否满足条件1和2，满足则top=mid-1，否则base=mid+1。最后base就是我们所需要的答案。
有人会问为什么去页数最多不是最少？最少当然也可以，但是别忘了条件1，每份工作量不大于ans，因此最小没有意义。而且甚至如果二分时判断每份工作量不大于ans的代码有问题，反而还可能会导致错误。
时间复杂度是O(NlogM)，其中M为所有数字之和,N为书的数目
#include <stdio.h>long long book[502];bool check(long long mid, int m, int k){int cnt = 0;long long sum = 0;for(int i = 1; i <= m; i ++){if(sum + book[i ] > mid){cnt ++;sum = book[i ];}elsesum += book[i ];}cnt ++;if(cnt <= k) return true;else return false;}int main(){int N;scanf("%d", &N);while(N--){int m, k;scanf("%d%d", &m, &k);long long top = 0;long long base = 0;for(int i = 1; i <= m; i ++){scanf("%lld", &book[i ]);top += book[i ];if(book[i ] > base)base = book[i ];}while(top >= base){long long mid = (top + base) / 2;if(check(mid, m, k))top = mid - 1;elsebase = mid + 1;}printf("%d\n", base);}return 0;}
