洛谷P1182 数列分段 Section II

P1182 数列分段 Section II - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题和 洛谷P3853 [TJOI2007]路标设置 、 洛谷P2678 [NOIP2015 提高组] 跳石头 思路做法类似，这里不过多赘述。

下面附上我写的代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
 
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
 
	int r = 1e9;
	int l = *max_element(a, a + n);//该函数是求a数组里的最大值 显然l必然>=该最大值 
	//int l = 1;这里这样写不行会使后面判断错误 这个自行体会 
	while (l < r)
	{
		int cnt = 0;
		int sum = 0;
		int mid = l + r >> 1;
		
		for (int i = 0; i < n; i++)
		{
			if (sum + a[i] <= mid) sum += a[i];
			else
			{
				i--;
				sum = 0;
				cnt++;
			}
		}
		if (sum > 0) cnt++;
		
		if (cnt <= m) r = mid;
		else l = mid + 1;
	}
	
	cout << l;
	return 0;
}