使最大值最小化/Uva 714/二分/贪心

• 按照题目意思，我们需要找一个x，使得每组被分到的书的总页数都小于x，且这个x得最小。
• 很明显，这个x的范围是：max~sum之间的，我们只需要从小到大枚举这么多数字，然后让检验是否满足前面一个条件即可。但是，分组的时候一定是贪心的分，即每个组被分到的书的总页数都尽量要贴近x，这样x才有可能是最小的，当需要的抄写员过多的时候，x一定小了，一定要抄写员等于所给的k的第一个x就是答案。
• 降低时间复杂度：搜索的数字是单调递增的，很明显选择二分，但是使抄写员正好等于x的可能有很多，我们需要找到这个序列中的第一个，因为这样才是最小的。

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;

const int maxn = 500 + 5;
LL p[maxn];
int n,k;

int solve(LL maxp){
    int done = 0,ans = 1;
    for(int i = 0;i < n; ++i){
        if(done + p[i] <= maxp){
            done += p[i];
        }
        else{
            done = p[i]; ans++;
        }
    }
    return ans;
}

int main(void){
    
    scanf("%d%d",&n,&k);
    LL tot = 0;
    LL maxp = -1;
    for(int i = 0;i < n; ++i){
        scanf("%d",&p[i]);
        tot += p[i];  maxp = max(maxp,p[i]); //pay attention to the use of function of max
    }
    
    LL L = maxp,R = tot;
    //这里是开始搜索 可以使得每组人分的序列和 都小于x的 最小x
    //如果选定了某个x，如何分组：那就是贪心了，为了都逼近且不超过x 都应该贪心的去拿 可以反证证明
    //而除了在满足正好k个人的max Page里搜最小的
    //而假如组数过少 或者过多 max page都要相应的缩小区间
    while(L < R){
        LL M = (L + R) / 2;
        if(solve(M) <= k) R = M; //由于是二分搜索 而非从小到大枚举 所以这里一定要找到可以满足条件的最小值
        else L = M + 1; //假如分的人大于k了，也就说明每个人分少了
    }
    printf("%d",L);
    return 0;
}

/*
9 3
100 200 300 400 500 600 700 800 900
*/