二分就是fw算法,不服来辩
  • 板块灌水区
  • 楼主BK小鹿
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/8/23 10:12
  • 上次更新2024/8/23 10:14:54
查看原帖
二分就是fw算法,不服来辩
1345783
BK小鹿楼主2024/8/23 10:12

标题只是吸引你进来的QAQ,大佬帮忙看看我哪写挂了吧QAQ。。。

我 ll 先赋值的 11,看了题解改成了最大值,结果还是不对,不理解了。。。

题目

WA Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000005;

int n, m;
int a[N];

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

int main()
{
	int l = 0, r = 0, mid;

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("d", &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;
	}

	printf("%d\n", l);
	return 0;
}
2024/8/23 10:12
加载中...