关于二分问题的另一种解法
2024-12-04 18:41:33
发布于:浙江
关于二分问题的另一种解法
本文将介绍对于一般「二分」问题的「二进制拆分」解法。
传统解决「二分」问题的方法为找到答案区间的上界和下界,划分 mid
并根据check(mid)
的结果来缩小区间,逼近答案;
而使用「二进制拆分」的方法则不用「显性」地使用区间上下界来逼近答案,不论是从原理上,复杂度分析上,还是从代码上也许都更易理解,本文将详细讲解此方法在各种「二分」问题中的应用。
简述
对于一般的二分问题,总是存在一个 ,把答案区间分成两个部分,左边为 右边为 ,反之亦然,我们假设 为左边区间的最后一个值。
假定问题的答案区间为 ,我们有以下代码,求出 :
int k = 0;
for (int i = 30; i >= 0; --i)
if (check(k + (1 << i)))
k += 1 << i;
原理
在介绍此方法前,我们需要确定以下事实:
- 任何正整数都可以拆分成 的整数次幂之和;
- ;
- 对于二分问题的答案区间 存在 使得 区间内的答案满足性质 , 区间内的答案满足性质 ,即「区间二分性」。
我们来看比较简单的一种情况,即在长度为 的有序数组 中查找第一个大于等于 的下标。
令最终查询结果的下标为 ,那么:
- 整个数组 中的所有元素全部小于 ,即 ;
- 整个数组 中的所有元素全部大于等于 ,即 。
即满足上文中的「区间二分性」。
我们考虑 的二进制形式,假定 ,其二进制形式为 ;
由于 ,所以我们从高位到低位枚举 的整数次幂,并令 :
- 对于 ,有 落在区间 中,那么我们令 。
- 对于 ,有 落在区间 中,那么我么令 。
- 对于 ,有 落在区间 中,所以我们什么也不做。
- 对于 ,有 落在区间 中,那么我么令 。
- 对于 ,有 落在区间 中,所以我们什么也不做。
- 对于 ,有 落在区间 中,那么我么令 。
最终我们得到了 。
当然具体在执行时,我们要考虑 是否处于数组范围内。
其 代码就像下面这样:
int p = -1;
for (int i = log2(n); i >= 0; --i)
if (p + (1 << i) < n and a[p + (1 << i)] < x)
p += 1 << i;
这里 初始化为 ,是因为 的整数次幂无法表示 。
对于 的初始值的取法,假定答案的最小值为 , 最大值为 , 取 即可。
简单来说,不考虑上界太大导致的异常问题,在值域规模不超过 时, 可以取 ;在值域规模不超过 时, 可以取 ,以此类推。
一个小优化
我们可以在初始化与取值时,直接取 的整数次幂,从而简化程序。
int k = 0;
for (int i = 1 << 30; i > 0; i >>= 1)
if (check(k + i)) k += i;
例子
对于二分查找问题:A8022.查找,我们可以有如下代码解决:
#include <bits/stdc++.h>
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
while (m--) {
int x; std::cin >> x;
int p = 0;
for (int i = 1 << 20; i > 0; i >>= 1)
if (p + i <= n and a[p + i] < x) p += i;
std::cout << (p < n and a[p + 1] == x ? p + 1 : -1) << ' ';
}
return 0;
}
对于二分答案问题:A20952.砍树,我们可以有如下代码解决:
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::cin.tie(0)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::vector<int> arr(n);
for (auto &x : arr) std::cin >> x;
auto check = [&](int h) {
i64 res = 0;
for (int i = 0; i < n; ++i)
res += std::max(0, arr[i] - h);
return res >= m;
};
int res = -1;
for (int i = 1 << 20; i > 0; i >>= 1)
if (check(res + i)) res += i;
std::cout << res << '\n';
return 0;
}
答案区间包含负数
类似于上面提到的 的整数次幂无法表示 的问题,我们可以转化以下问题,把 初始化为答案的下界,而在二进制枚举的过程中,我们枚举的值为最终答案与下界的「差」,即可。
答案区间为实数域
对于实数,其可以用二进制近似地表示,所以我们可以更改循环结束的条件和取 的方法,使得其在 时依然正确,从而可以将其应用到实数域上的二分问题。
double k = 0.0;
for (int i = 30; i >= -30; --i)
if (check(k + pow(2, i)))
k += pow(2, i);
全部评论 3
开始学习📑
14小时前 来自 浙江
1强强强
14小时前 来自 广东
0沙发
14小时前 来自 广东
0
有帮助,赞一个