- 单调有序集合或函数中查找一个解
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;
}
