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

推荐订阅源

Martin Fowler
Martin Fowler
博客园 - 三生石上(FineUI控件)
WordPress大学
WordPress大学
博客园_首页
宝玉的分享
宝玉的分享
S
SegmentFault 最新的问题
Jina AI
Jina AI
Hugging Face - Blog
Hugging Face - Blog
V
Visual Studio Blog
美团技术团队
IT之家
IT之家
罗磊的独立博客
Blog — PlanetScale
Blog — PlanetScale
Google DeepMind News
Google DeepMind News
月光博客
月光博客
Microsoft Azure Blog
Microsoft Azure Blog
H
Help Net Security
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
Last Week in AI
Last Week in AI
博客园 - 叶小钗
M
MIT News - Artificial intelligence
B
Blog RSS Feed
有赞技术团队
有赞技术团队
Y
Y Combinator Blog

博客园_首页

Linux实操--组管理、权限管理和定时任务 Java + EasyExcel 实现单个接口导出多个Excel Mem0 源码解析系列(二):提示词工程的深度剖析 Openclaw TaskFlow究竟是什么?和普通Skill技能有什么区别 博文阅读密码验证 - 博客园 嘉立创开源:应该是全网MicroPython教程最多的开发板 Hermes Agent 集成实践:从协议到生产 2026年AI编程工具横评:Cursor、Codex、Claude Code、Zed、Windsurf Java程序员必看的RAG入门教程 2026 AI效率神器:Superpowers + Claude Code 保姆级教程 本地大模型部署全攻略:从 0 到 1 玩转 Ollama 【从0到1构建一个ClaudeAgent】内存管理-上下文压缩 .NET 高级开发 | 设计、实现一个事件总线框架 电子小白入门之NE555 3. WorkBuddy:隐藏玩法,一键召唤专家,让 AI 以"专家身份"给你干活 和AI一起搞事情#3:Claude Teammate 游戏开发翻车实录 【OpenClaw】通过 Nanobot 源码学习架构---(7)Memory C# .NET 周刊|2026年3月3期 我在 Debian 11 上把 K8s 单机搭起来了,过程没你想的那么顺(/opt 目录版) 深度学习进阶(七)Data-efficient Image Transformer CLI+Skill搭建浏览器AI自动化框架,告别一切重复枯燥任务 告别Token账单无底洞:OpenClaw本地部署,重塑企业数据主权的唯一解 FastAPI+Vue:文件分片上传+秒传+断点续传,这坑我帮你踩平了! SBTI 爆火后,我做了个程序员版的 CBTI。。已开源 + 附开发过程 多模态检索开始进入工程期:用 Sentence Transformers 搭建可落地的 Multimodal RAG 100多行代码实现一个最简单的Agent(用ReAct) Claude Code 通关手册(八):推荐 5 个 Hooks,代码质量提升 3 倍 老板:“有人截图了!”。安全部门:“收到,马上查暗水印!” - why技术 技术之外,皆是人间 C#/.NET/.NET Core技术前沿周刊 | 第 69 期(2026年4.01-4.12)
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;
}