惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

L
LangChain Blog
V
V2EX
爱范儿
爱范儿
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
Martin Fowler
Martin Fowler
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
Apple Machine Learning Research
Apple Machine Learning Research
WordPress大学
WordPress大学
有赞技术团队
有赞技术团队
宝玉的分享
宝玉的分享
Last Week in AI
Last Week in AI
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
罗磊的独立博客
小众软件
小众软件
Vercel News
Vercel News
博客园 - 司徒正美
阮一峰的网络日志
阮一峰的网络日志
V
Visual Studio Blog
J
Java Code Geeks
P
Proofpoint News Feed
MongoDB | Blog
MongoDB | Blog
B
Blog
美团技术团队
量子位

博客园_首页

Plist 二进制格式 Milvus 和 PGVector,哪个更好? OpenClaw 已过时?在 VS Code 中运行 Hermes Agent! 第30篇文章:一个大三计科生的自白 Manim如何在数学公式中完美显示中文? Docker 部署 RocketMQ 5 并发编程核心概念辨析 C#事务处理最佳实践:别再让“主表存了、明细丢了”的破事发生 CLI 是什么?为什么大厂突然集体卷命令行? 【从0到1构建一个ClaudeAgent】协作-自主Agent UIImageView 设置图片不生效的原因排查 最小二乘问题详解20:无先验约束下的增量式SFM自由网平差 痞子衡嵌入式:大话双核i.MXRT1180之XIP应用里借助MU实现可靠Flash IAP的方法 AI Chat 封装, SemanticKerne.AiProvider.Unified 已发布 Windows下右键编辑js文件无法打开记事本——在注册表中使用环境变量 在后台服务中使用 Scoped 服务,为什么总是报错? H200 安装驱动并使用sglang启动模型 wireshark 抓包Trap上报告警内容 我用 AI 辅助开发了一系列小工具(2):图片压缩工具 [A Primer On MC and CC] 2.1 Memory Consistency 1 - 指令重排序和 SC 模型 Oracle数据库SCN推进技术详解与实践指南 玩转控件:封装个带图片的Label控件 Claude Code 4.7 真正该升级的不是模型,而是你的工作流 前端小白一句话,AI 帮我做了个颜值拉满的桌面媒体播放器。当代码不再是门槛,一句话编程就是现实。 5. WorkBuddy: 小龙虾的灵魂三件套,让你的小龙虾不只是工具 SQLite 分片方案实战:三种分片策略的深度对比 告别简陋 UI!一款基于 Fluent Design 和基于 WinUI 的开源免费、现代化的 Avalonia UI 控件库 关于二进制排列组合枚举的总结 AI开发-python-LangGraph框架(3-27-LangGraph从零实现大模型智能决策工作流) ElasticSearch主分片和副本分片概念详解
Educational Codeforces Round 175 (Rated for Div. 2) C
不太会a · 2026-05-17 · via 博客园_首页

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\),我们遍历每一个格子:

  1. 必须要涂对(\(a_i > x\):惩罚值太高了,我们承受不起它出错!
  • 如果期望是 'B':那它必须被涂蓝。
  • 如果期望是 'R':那它绝对不能被涂蓝(相当于一堵墙,强行打断当前的涂色操作)。
  1. 无所谓(\(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;
                    }
                }
                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;
}