大佬们求助 这样子写二分过不了
查看原帖
大佬们求助 这样子写二分过不了
592775
acwww楼主2022/3/19 23:50

把check里面换成<= 二分r=mid l=mid+1就能过是为什么

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;
int check(int x)
{
	int res = 0, d = 0;
	for (int i = 1; i <= n; i++)
	{
		res += a[i];
		if (res >x)
		{
			res -= a[i];
			i--;
			d++;
			res = 0;
		}
		else if (res == x)
		{
			d++;
			res = 0;
		}
	}
	if (res != 0) d++;
	return d < m;
}
int main()
{
	cin >> n >> m;
	int temp = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		temp = max(temp, a[i]);
	}

	int l = temp, r = 1e9 + 7, mid;
	while (l < r)
	{
		mid = l + r+1  >> 1;
		if (check(mid))
		{
			r = mid-1;
		}
		else
		{
			l = mid;
		}
	}
	cout << l;
}

2022/3/19 23:50
加载中...