二分答案刷题4

发布时间:2024年01月22日
题目来源:数列分段 Section II - 洛谷

这道题又是一道求最值的问题,求每段和的最大值最小,可以用二分答案求解。

解题思路:

?二分答案求解的过程中,最重要的是判断条件,判断条件想好就迎刃而解了。确定一个bool类型,用来检查是否能将数组分成不超过 M 个连续的段,使得每个段的和不超过 最小的每段和的最大值。

解题步骤:

1、确定判断条件check函数:

  1. ?初始化变量:

    • count = 1: 表示分段数。初始化为 1,因为至少会有一个分段。
    • long long segSum = 0: 表示当前段的和。
  2. ?遍历数组:

    • 循环遍历数组 a 中的每个元素。
  3. 检查当前段和:

    • 如果当前段的和 segSum 加上当前元素 a[i] 超过了 minSum,这意味着不能把当前元素加入当前段,因为这会使段和超过 minSum
    • 因此,需要开始一个新的段,将 count(段数)加一,并将 segSum 重置为当前元素的值 a[i],表示新段的开始。
  4. 累加当前段和:

    • 如果当前段的和 segSum 加上当前元素 a[i] 不超过 minSum,则可以将当前元素加入当前段中,所以 segSum 加上当前元素的值。
  5. 返回是否符合条件:

    • 最后,检查分段的数量 count 是否不超过允许的最大段数 M
    • 如果 count <= M,返回 true,表示可以将数组分割成不超过 M 段,且每段的和不超过 minSum
    • 如果 count > M,返回 false,表示无法在这个 minSum 下将数组分割成 M 或更少段。

2、 用二分查找,从中间开始搜索。注意的是,low设置为数组中的最大值,high设置为整个数组的和。(因为分段中最大不会超过总的和,最小也是分段中的元素最大值。)

#include<iostream>
#include<algorithm>
#include <numeric> 
using namespace std;
#define maxn 100000010
long long  a[maxn];
long long N, M;



bool check(int minSum)
{
	int count = 1;// 初始化为 1,因为至少有一个段
	long long segSum = 0;//当前段的和
	for (int i = 0; i < N; i++)
	{
		if (segSum + a[i] > minSum)
		{
			count++;
			segSum = a[i];
		}
		else {
			segSum += a[i];
		}
	}
	return count <= M;


}
int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	int low = *max_element(a, a + N);
	int high = accumulate(a, a + N, 0);
	int ans;
	while (low <= high)
	{
		int mid = low + (high - low) / 2;
		if (check(mid))
		{
			ans = mid;
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
	cout << ans << endl;
	return 0;

}

题目来源:[TJOI2007] 路标设置 - 洛谷

PS:这道题我只能做到100分,没有完全accept。(大家看看就好)

?

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 1000010
int a[maxn];
long long  L, N, K;

bool check(int minD)
{
	int remove = 0;
	for (int i = 1; i < N ; i++) {
		int gap = a[i] - a[i - 1];
		remove += (gap - 1) / minD;
	}
	return remove <= K;
}

int main()
{
	cin >> L >> N >> K;
	for (int i = 0; i <N; i++)
	{
		cin >> a[i];
	}

	int low = 0, high = L, mid, ans = 0;
	while (low < high)
	{
		mid = low + (high - low) / 2;
		if (check(mid))
		{
			ans = mid;// 如果可以实现这个距离,则尝试更大的距离
			high = mid;
		}
		else {
			low = mid + 1;// 如果不可以,则尝试更小的距离
		}
	}

	cout << ans << endl;
	return 0;
}

文章来源:https://blog.csdn.net/weixin_56642379/article/details/135669087
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。