C++-洛谷每日一题

数列分段 Section II - 洛谷https://www.luogu.com.cn/problem/P1182这道题是一道经典的二分题目， 蓝桥的分糖果和这道题基本一模一样。

代码：

#include 

using namespace std;

const int N = 100010;

int n, m;
int a[N];

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

int main()
{
	cin >> n >> m;
	
	int l = 0, r = 0;
	for(int i = 1; i <= n; i ++ )
	{
		scanf("%d", &a[i]);
		l = max(l, a[i]);
		r += a[i];
	}
	
	while(l < r)
	{
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	
	cout << l;
	
	return 0;
}

其实这道题对于大家来说基本没什么难度， 但是身为蒟蒻的我满怀信心的交了之后却WA了

我看了看题解发现了问题所在， 左端点不能取0或1。

关于这个点我也不是特别清楚， 我太菜了

所以发布了这片文章，提醒大家在这种题型的二分时左端点取数组中的最大值，右边就取sum就好了。