1436：数列分段II -整型二分

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;
}