当前位置：首页 > news >正文

【codeforces 2070c】二分答案详解

news 来源：原创 2025/8/23 7:30:33

【codeforces 2070c】二分答案详解

二分答案转化成判定

对于任何问题，如果我们有了一个判定算法，那把解空间枚举并判定一遍，当然就可以得到解了。而当解空间具有单调性时，我们就可以使用二分法代替枚举。

考虑如下问题：

有 $n$ 本数排成一行，已知第 $i$ 本的厚度是 $a_i$ 。把它们分成连续的 $m$ 组，使 $T$ 最小化，其中 $T$ 是厚度之和最大的一组的厚度。

考虑性质：是否存在一种划分方案，使得 $\leq x$ 。也就是说，是否存在一种连续划分 $m$ 组的方式，使得每组厚度都小于等于 $x$ 。若 $f (x) = t r u e$ ，则 $f (x + 1) = t r u e$ 。满足单调性，可以二分。

请大家体会这里的性质为什么是 $\leq x$ ，而不是等于 $x$ 。只要这样，当 $f (x) = t r u e$ 时，可以推得 $f (x + 1) = t r u e$ ；因为小于等于 $x$ 成立，小于等于 $x + 1$ 必然成立。

Problem - C - Codeforces

给定 $n$ 个单元格组成的长条，初始时所有单元格都是红色。每次操作，都可以选择一段连续的单元格并将其涂成蓝色。对于每个单元格，给出所有操作后指定的颜色：红色或蓝色。现规定只能进行 $k$ 次操作。显然，不可能总是在 $k$ 次操作中完成满足所有要求。因此，每个单元格都有一个惩罚值。如果单元格在所有操作后的颜色是错误的，惩罚值就会生效。定义最终的惩罚值是是所有单元格生效的惩罚值中最大的。若没有生效的，则为 $0$ 。问最小的最终惩罚值是多少？

考虑二分答案。性质：是否存在一种合法的涂色方案，使得惩罚值小于等于 $x$ ？将该性质记为 $f (x)$

若存在一种合法的涂色方案使得惩罚值小于等于 $x$ ，就存在一种合法的涂色方案使得惩罚值小于等于 $x + 1$ 。即，若 $f (x) = t r u e$ 则 $f (x + 1) = t r u e$ 。该性质单调，可以二分。

该性质可以理解为：如果一个单元格的惩罚值小于等于 $x$ ，我们无需关心该单元格的颜色是否正确。如果一个单元格的惩罚值大于 $x$ ，我们就必须将该单元格涂成正确的颜色，否则，惩罚值将会被该惩罚值更新。按以上策略考虑，操作次数为 $res$ 。最终检验 $\leq k$

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"#define x first
#define y second
#define int LLconst int N = 3e5 + 10;
string str;
int n, k, a[N];void solve() {cin >> n >> k >> str;str = " "  + str;for (int i = 1; i <= n; i ++) cin >> a[i];int l = 0, r = *max_element(a + 1, a + n + 1);auto check = [&](int mid) -> bool {vector<pair<int, int>> op;for (int i = 1; i <= n; i ++) {if (a[i] <= mid);else {if (str[i] == 'R') op.push_back({i, 0});else op.push_back({i, 1});}}int res = 0, i = 0, last = -1;while (1) {if (op[i].y == 1) {if (last == -1) last = op[i].x;i ++;}else if (op[i].y == 0) {if (last == -1);else res += 1;last = -1;i ++;}if (i >= op.size()) {if (last != -1) res ++;break;}}return res <= k;};while (l < r) {int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << r << endl;
}signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t; cin >> t;while (t --) solve();return 0;
}

102. 最佳牛围栏 - AcWing题库

给定正整数数列 $a$ ，求一个平均数最大的，长度不小于 $L$ 的连续字段

考虑性质：是否存在一种合法的方案(长度不小于 $L$ )，使得平均值大于等于 $x$

若 $f (x) = t r u e$ ，则 $\ x' \leq x$ ；若 $f (x) = f a l se$ ，则 $\ x' \geq x$

可以二分。

若将 $a$ 中所有数减去平均数 $x$ ，则判断是否存在合法字段和非负。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl "\n"const int N = 1e5 + 10;
int n, m;
double a[N], t[N];bool check(double mid) {t[0] = 0;for (int i = 1; i <= n; i ++) {t[i] = a[i] - mid;}for (int i = 1; i <= n; i ++) {t[i] += t[i - 1];}double minv = 1e18;for (int i = 0, j = m; j <= n; j ++, i ++) {minv = min(minv, t[i]);if (t[j] - minv >= 0) return true;}return false;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i ++) cin >> a[i];double l = 0, r = 1e18;while (r - l > 1e-5) {double mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}cout << (int)(r * 1000) << endl;return 0;
}

【codeforces 2070c】二分答案详解

相关文章：