1436：数列分段II
题目来源：一本通

【输入样例】

5 3
4 2 4 5 1

【输出样例】

6

题意

将数列分成若干段，最多M段，求这些段中最大值中的最小值。（M<=N是M的约束）

思路

• 最大最小问题考虑二分。由于M越大，则每段的平均值越小，即里面的最大值的越小。M作为约束，所以当分段>M作为check()函数跳出条件
• 题目没给数据范围，所以二分区间可以选择[min(a[i])，max(sum(a[i])]（当然，简单点就直接设[0,1e10]，不会超时），而M作为约束条件

数据约束

无

注意事项

哈哈，总有一个样例过不了。检查一下代码，发现有漏洞，始终要清醒：t必须是当前子段和最大值，但当a[i]>t，sum=a[i] 然后进入下一个循环，所以就有Bug。因此需要单独判断a[i],如果>t 就不符合条件。

eg：4 1 4 5 2 很显然有数据5，当Mid=4就不可能成立

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N =1000000; 
int n,m,a[N];
bool check(int t);//判断是否有m段 
int main()
{cin>>n>>m;int l = 0, r = 0;for(int i=0;i<n;i++){cin>>a[i];l = min(l,a[i]) ;r += a[i];}//二分int anwser = 0;while(l<=r){int mid = (r+l)/2;if(check(mid)) {anwser = mid;r= mid-1; //必须要区间保证是收敛的（不断缩小的） }else l = mid+1;} cout<<anwser;return 0;
}
bool check(int t){int sum = 0,ans = 1;//默认为a[0]容易有Bug 万一a[0]>m那就凉凉 for(int i=0;i<n;i++){if(a[i]>t){ //段里面的单个数据不能超过t否则出错 return false;}sum += a[i];
//		if(t ==5 ) cout<<sum<<"/"<<i<<"   "<<ans<<endl;//判断ans的情况，因为ans比m大，说明t可以分更小 ，也就是字段和不是最小值 if(sum>t){//因为t是sum里面的最大值，所以必须保证sum<=t sum = a[i];ans++;}if(ans>m){return false;}}return true;
}