九度 1502：最大值最小化(二分法)

题目描述：

在印刷术发明之前，复制一本书是一个很困难的工作，工作量很大，而且需要大家的积极配合来抄写一本书，团队合作能力很重要。
当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书，编号为1,2,3...m, 每本书有1<=x<=100000页， 把这些书分配给k个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，你的任务就是找到一个最佳的分配方案，使得所有书被抄完所用的时间最少。

 

思路

1. kedebug 上似乎做过这道题, 二分搜索变形题, 看到最大值最小化和最小值最大化都应该往这方面考虑, 应该需要总结一下

 

 

代码

#include <iostream>
#include <stdio.h>
using namespace std;

int m,k;
int books[600];


int main() {
int n;
    scanf("%d", &n);
for(int i = 0; i < n; i ++) {
        scanf("%d%d",  &m, &k);

int high = 0, low = 0;
for(int i = 0; i < m; i ++) {
            scanf("%d", books+i);
            high += books[i];
            low = max(low, books[i]);
        }

//printf("high = %d, low = %d\n",high, low);
while(low <= high) {
int mid = (low + high) >> 1;

int cnt = 1, sum = 0;
for(int i = 0; i < m; i ++) {
if(sum + books[i] <= mid) {
                    sum += books[i];
                }else{
                    cnt ++;
                    sum = books[i];
                }
            }

if(cnt <= k) {
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }

        printf("%d\n", low);

    }
return 0;
}