https://codeforces.com/problemset/problem/2070/C
核心题意解析
简单来说：
- 我们有一条长度为 \(n\) 的纸带，初始全为红色
'R'。 - 我们最多可以选 \(k\) 个连续段，把它们涂成蓝色
'B'（涂了不能撤销）。 - 每个格子有一个期望颜色和一个“惩罚值” \(a_i\)。如果最终颜色和期望颜色不符，就会产生 \(a_i\) 的惩罚。
- 目标：在最多操作 \(k\) 次的前提下，让所有颜色错误的格子中，惩罚值的最大值尽可能小。
最大化最小值
遇到最大化最小值基本套路就是贪心和二分，解题的时候优先往这个方向想。
Hint1:二分
直接求“最小的最大惩罚值”很难无从下手，但如果我们换个角度问自己：“假设我最高只能容忍 \(x\) 的惩罚值，我能不能在 \(k\) 步内搞定？” 这个问题就简单多了。
- 如果 \(x\) 容忍度很高，那很容易做到。
- 如果 \(x\) 容忍度很低，那可能 \(k\) 步根本不够用。
这种单调性完美契合二分查找的特性。
Hint2:贪心 Check 函数的策略
假设当前的容忍极限是 \(x\)，我们遍历每一个格子：
- 必须要涂对（\(a_i > x\)）：惩罚值太高了，我们承受不起它出错！
- 如果期望是
'B'：那它必须被涂蓝。 - 如果期望是
'R'：那它绝对不能被涂蓝（相当于一堵墙，强行打断当前的涂色操作）。
- 无所谓（\(a_i \le x\)）：就算错了惩罚值也没超过 \(x\)，所以它变成什么颜色我们根本不关心。顺其自然即可（能省操作就省操作）。
贪心策略：从左到右遍历，遇到“必须是蓝色”的格子且当前没在涂色，就消耗 1 次操作开启一个新的涂色段；遇到“必须是红色”的格子，就强行结束当前涂色段；遇到“无所谓”的格子，保持当前状态直接跳过。最后看总操作数是否 \(\le k\)。
最终代码
点击查看代码
//
// Created by awake on 2026/5/14.
//
#include <bits/stdc++.h>
using namespace std;// clang-format off
struct { auto operator()(auto &i) { cin >> i; } } IN; // NOLINT
struct { auto operator()(auto &i) { cout << i << ' '; } } OUT; // NOLINT
// clang-format on
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)// NOLINT
using ll = long long; //NOLINT
template <typename T>
using vec = vector<T>; //NOLINT
#define int long long
#define endl '\n'void solve()
{int n, k;cin >> n >> k;string s;cin >> s;vec<int> a(n);ranges::for_each(a, IN);auto check = [&](int x){int cnt = 0;bool blue = false;for (int i = 0; i < n; i++){if (a[i] > x){if (s[i] == 'B'){if (!blue){cnt++;blue = true;}}elseblue = false;}}return cnt > k;};int l = 0, r = 1e9 + 1;auto ran = views::iota(l, r);auto ans = *ranges::partition_point(ran, check);cout << ans << endl;
}signed main()
{IOS;int T;cin >> T;while (T--)solve();return 0;
}