https://codeforces.com/problemset/problem/2070/C
简单来说：
'R'。'B'（涂了不能撤销）。遇到最大化最小值基本套路就是贪心和二分，解题的时候优先往这个方向想。
直接求“最小的最大惩罚值”很难无从下手，但如果我们换个角度问自己：“假设我最高只能容忍 \(x\) 的惩罚值，我能不能在 \(k\) 步内搞定？” 这个问题就简单多了。
假设当前的容忍极限是 \(x\)，我们遍历每一个格子：
'B'：那它必须被涂蓝。'R'：那它绝对不能被涂蓝（相当于一堵墙，强行打断当前的涂色操作）。贪心策略：从左到右遍历，遇到“必须是蓝色”的格子且当前没在涂色，就消耗 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;
}
}
else
blue = 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;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。