洛谷P1182 数列分段 Section II 【贪心+二分】

题目链接：P1182 数列分段 Section II

程序说明：

二分适用于区间有界且单调，例如最大值最小或者最小值最大这类问题。

设区间所有数中的最大值为L，区间所有的数总和为R，则答案一定位于L和R之间。利用二分算法快速得出答案。check函数利用贪心的思想，即P1181 数列分段Section I的方法，判断mid是否满足题目要求，如果不满足则在相应的区间进行二分查找。

代码如下：

#include <iostream>
using namespace std;
const int N = 100010;
int a[N], n, m; 
bool check(int x) {
	int tot = 0, cnt = 1;
	for(int i = 0; i < n; i++) {
		tot += a[i];
		if(tot > x) {
			cnt++;
			tot = a[i];
		}
	}
	//如果所分的段数大于m，返回true 
	return cnt > m;
}
int main() {
	cin>>n>>m;
	int l = 0, r = 0, mid;
	//l是区间最大值，r是区间总和 
	for(int i = 0 ; i < n; i++) {
		cin>>a[i];
		l = max(l, a[i]);
		r += a[i];
	}	
	while(l <= r) {
		mid = l + r >> 1;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout<<l;
	return 0;
}