7183-数列分段 II

先读懂题意 ：对长度为$N$的整数数列，划分成$M$段，然后让和最大的那段，尽可能的小。
这个和是多少，我们并不知道，所以需要搜索。那么当搜某个和的时候，需要计算数列能不能划分成$M$段，如果可以，则找到其中一个答案，如果用枚举，应从小到大枚举，只要符合能划分$M$段，就找到了最优解。
就算是枚举，也要考虑枚举范围，显然最大值为整个整数数列之和，而初值则应该是这个数列中的最大值。那是因为，最大的那个数，无论如何划分，它肯定会属于某一段，那么和最大的那段的总和必然不会小于它，所以初值因为这个数列的最大值。
枚举写法如下：

for(int 答案=数列的最大值; 答案<=数列之和; 答案++){
	int 区间和=0;
	int 段数=0;
	for(int i = 1; i <= n + 1; i++){
		区间和+=a[i];
		if(区间和>答案){
			段数++;
			区间和=a[i];
		}
	}
	if(段数==M){
		cout<<答案;
		return 0;
	}
}

扫描到$n+1$是一种编程技巧，因为只有区间和大于答案的时候，才更新段数，所以最后一段不会统计进去，解决方式：增加第$n+1$个元素，给一个大数。此题，进入搜索前：a[n+1]=1e9。
上面纯暴力的写法，结果免不了超时，但这个过程是初学二分答案的必经阶段，除非你的阅读理解分级达到了4级（../../../阅读理解分级（你是几级？）），一眼能看出题目考察的算法。
继续分析，答案验证必不可少，否则无法判断答案是否符合要求，所以超时主要是因为答案枚举上，即验证了很多无效答案。
那么这题中，答案是否具有二分特性？

一般，大于和小于必然是相反方向，而等于会和其中一个同一方向，一种比较容易的思考方式：想不符合的是哪种情况，确定方向后，剩下的是另一个方向。
通过刚才的分析，确定答案具有二分特性。
总结：

• 答案区间：$[\mathrm{数}\mathrm{列}\mathrm{元}\mathrm{素}\mathrm{最}\mathrm{大}\mathrm{值}，\mathrm{数}\mathrm{列}\mathrm{元}\mathrm{素}\mathrm{之}\mathrm{和}]$
• 预处理a[n+1]=1e9
• 符合条件找最小，确定模板为往左寻找的二分答案模板。
• 答案验证：区间求和，超过答案，找到一段。
  答案验证部分，改写枚举代码中的验证：

bool check(int x)
{
	int sum = 0, cnt = 0;
	for(int i = 1; i <= n + 1, i++){
		sum += a[i];
		if(sum>x){
			cnt++;
			sum = a[i];
		}
	}
	return cnt<=m;
}