二分(TOJ 2789)

• 单调有序集合或函数中查找一个解

Q：给出n天中每天的花费，需将这些天分成m组，每组包含连续的一天或多天，若定义第i组的花费为Ki，求一种分组方式使得K=max{Ki}最小
输入第一行为两个正整数N M之后输入N个正整数，分别表示第i天的花费，输出求得的K

输入样例
7 5
100
400
300
100
500
101
400
输出样例
500

二分.jpg

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
int n,m;
int a[100002];
bool check(int top){
    int num=1;//组数
    int cur=0;//当前组的总耗费
    for(int i=0;i<n;++i){
        if(cur+a[i]<=top)
             cur+=a[i];
        else{
            ++num;//再开一组
            cur=a[i];//重新初始化总耗费
        }
    }
    //求出了再当前top的限定下最少可以分多少组
    //若这个组数小于m则就符合题意因为分的组更多每组耗费就越少
    //然后就是要在符合题意的当中找到那个最小的（再小下去就不符合题意了）
    return (num<=m);
}
int main()
{
    while(cin>>n>>m){
        int sum=0;
        int ma;
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            sum+=a[i];
            ma=max(ma,a[i]);
        }
        int low=ma,high=sum,mid;
        while(low!=high){
            mid=(low+high)/2;
            if(check(mid)) high=mid;//符合题意就可以往更小找
            else low=mid+1;
        }
        printf("%d\n",low);
    }
    return 0;
}