二分答案刷题

?题目来源：

? ? ? ? ? ? 1、? ?????[COCI 2011/2012 #5] EKO / 砍树 - 洛谷

? ? ? ? ? ? 2、?《深入浅出程序设计竞赛--基础篇》------汪楚奇P179

做题思路：

题目的需求是求最大的整数高度h，使得能够收集到的长度为m的木材。是一个求最值的问题，若通过枚举的方式求，时间复杂度则会非常高，本题的思路是用二分答案求解，将一个求最值的问题转换为判定问题，通过判定条件来验证某个候选答案是否可行。

二分答案的过程大致如下：

?1、确定搜索范围：首先确定答案可能存在的范围。本题范围是从 0 到树木中的最大高度。

?2、选择中间值进行验证：在确定的范围内选择一个中间值，验证这个值是否可行。检查在这个高度砍树能否得到至少 M 米的木材。

?3、根据验证结果调整搜索范围：如果中间值可行（即能砍到足够的木材），则可能存在更高的有效高度，所以向上调整搜索范围。如果不可行，向下调整搜索范围。(当木材总量等于 M 时，找到了正确的高度；如果总量大于 M，可以增加高度；如果总量小于 M，则降低高度)

?4、重复过程：重复步骤 2 和 3，直到找到最高的有效高度。

#include<iostream>
#include<vector>
#include<algorithm> 

using namespace std;


//函数用于计算在给定高度H时砍下的木材总量
long long woodCuts(const vector<int>& tree, int H)
{
	long long total = 0;
	for (int height : tree)
	{
		if (height > H)
		{
			total += (height - H);

		}
	}
	return total;
}

// 二分查找函数，寻找最大的锯片高度
int findMaxHeight(const vector<int>& trees, long long M) {
    int low = 0, high = *max_element(trees.begin(), trees.end());//high为树的最大高度
    int H = 0; // 最终的高度

    while (low <= high) {
        int mid = low + (high - low) / 2;
        long long cut = woodCuts(trees, mid);

        if (cut >= M) {
            H = mid; // 更新 H，尝试更高的高度
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }

    return H;
}

int main() {
    int N;
    long long M;
    cin >> N >> M;
    vector<int> trees(N);
    for (int i = 0; i < N; ++i) {
        cin >> trees[i];
    }

    int maxHeight = findMaxHeight(trees, M);
    cout << maxHeight << endl;

    return 0;
}

书上的源代码：

#include<iostream>
#include<vector>
#include<algorithm> 

using namespace std;

#define maxn 1000010
typedef long long LL;
LL a[maxn], n, m;
bool P(int h)  //当砍树高度为h时，能否得到大于m的木材
{
	LL tot = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] > h)
			tot += a[i] - h;
	return tot >= m;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int L = 0, R = 1e9, ans, mid;
	while (L <= R)
		if (P(mid = L + R >> 1))
			ans = mid, L = mid + 1;
		else
			R = mid - 1;
	cout << ans << endl;
	return 0;
}

参考二分 - OI Wiki可以看出，什么情况下可以考虑二分答案？解题的时候考虑枚举然后检验枚举的值是否正确时，若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。本题满足单调性，当砍树高度超过某个数时，不满足“条件”（收集m个木材）则不成立，而不超过这个数时，“条件”一定成立。符合二分条件！

此外书上备注如下：

使用二分答案技巧的条件：

1)命题可以被归纳为找到使得某命题P(X)成立(或不成立)的最大(或最小)的X。

2)把 P(x)看作一个值为真或假的函数,那么它一定在某个分界线的一侧全为真,另一侧全为假。

3)可以找到一个复杂度优秀的算法来检验 P(X)的真假。通俗来讲，二分答案可以用来处理“最大的最小”或“最小的最大”问题。