C. Limited Repainting 详细题解

问题理解

我们有一条由 $n$ 个格子组成的条带，初始时所有格子都是红色。
我们可以执行最多 $k$ 次操作，每次操作选择一段连续的格子，把它们全部涂成蓝色（覆盖之前可能是红色或蓝色的状态）。注意不能涂红色。

每个格子 $i$ 有一个目标颜色（$R$ 表示最终应为红色，$B$ 表示最终应为蓝色）和一个惩罚值 $a_i$。
如果某个格子最终的颜色与目标不同，就会产生惩罚，惩罚值等于 $a_i$。

最终整个涂色的代价定义为：所有颜色错误的格子中，惩罚值的最大值。如果没有格子颜色错误，代价为 $0$。

问：在最多 $k$ 次操作下，能达到的最小代价是多少？

---

核心思路

这是一个最小化最大值（min-max）问题，常用技巧是二分答案。

假设我们猜测一个代价 $d$，问：能否用不超过 $k$ 次操作，使得最终代价 $\le d$？

---

如何检查一个给定的 $d$ 是否可行

如果最终代价 $\le d$，那么任何惩罚值 $a_i > d$ 的格子都绝对不能错，否则代价会超过 $d$。
而惩罚值 $a_i \le d$ 的格子可以错，对代价没有影响（因为最大值由 $>d$ 的那些格子决定）。

所以问题转化为：
只考虑惩罚值 $> d$ 的格子，这些格子必须最终颜色正确。我们能否用不超过 $k$ 次涂蓝操作实现？

---

只考虑重要格子

对于这些“重要”格子（$a_i > d$）：

• 如果目标颜色是 $R$（红色）：初始就是红色，不需要任何操作。
• 如果目标颜色是 $B$（蓝色）：初始是红色，必须被至少一次涂蓝操作覆盖。

注意：涂蓝操作覆盖的是连续区间。我们可以选择多个区间，每次操作可以覆盖连续的一段重要蓝格子，以及中间可能夹杂的非重要格子（因为涂蓝会把它们也涂蓝，但非重要格子允许错，所以没关系）。

---

最少需要多少次操作

从左到右扫描所有重要格子（即 $a_i > d$ 的格子），只考虑那些目标为 $B$ 的重要格子：

• 用一个变量 last 记录上一个重要格子的颜色（只记录重要格子，忽略非重要格子），初始为 R。
• 当遇到一个目标为 $B$ 的重要格子时：
  • 如果上一个重要格子不是 B，说明需要开始一个新的涂蓝区间，操作数加 $1$。
  • 把 last 更新为当前格子的颜色（$B$）。
• 如果遇到目标为 $R$ 的重要格子，它不需要操作，但会打断连续蓝色区间的延续，所以 last 更新为 R。

这样统计出的操作次数 $cnt$ 就是最少需要的涂蓝操作数。

为什么这样贪心正确？
因为涂蓝一个区间可以覆盖连续的一段蓝色目标格子，遇到第一个需要蓝色的重要格子就开启新区间，不会浪费操作，也不会漏掉任何必须覆盖的格子。

---

检查条件

如果 $cnt \le k$，说明我们可以用不超过 $k$ 次操作使所有重要格子颜色正确，因此最终代价 $\le d$ 是可行的。

否则，如果 $cnt > k$，则无法在 $k$ 次操作内完成，代价必须大于 $d$。

---

二分答案框架

• 代价 $d$ 的最小可能值是 $0$（所有格子颜色正确时），最大可能值是 $\max(a_i)$（最坏情况）。
• 我们在这个区间内二分：
  • 取中点 $m$。
  • 检查是否可行（用上述贪心方法）。
  • 如果可行，说明答案可以更小，往左半区间搜索。
  • 如果不可行，说明答案必须更大，往右半区间搜索。
• 最后找到最小的可行 $d$，即为答案。

---

正确性证明

1. 单调性：如果某个 $d$ 可行（可以用 $\le k$ 次操作使代价 $\le d$），那么对于任意更大的 $d' > d$ 也一定可行（因为放宽了约束）。所以可行性关于 $d$ 是单调的，可以二分。

2. 贪心正确性：在只考虑重要格子时，涂蓝操作必须覆盖所有目标为 $B$ 的重要格子。由于每次操作涂一个连续段，最优策略就是让每个段尽可能长，即遇到第一个 $B$ 时开新区间，直到遇到 $R$ 才结束。这正是上面的扫描过程。

---

复杂度分析

• 二分范围是 $[0, \max(a_i)]$，最多 $\log(10^9) \approx 30$ 次检查。
• 每次检查扫描一次数组，$O(n)$。
• 总复杂度 $O(n \log M)$，其中 $M = 10^9$。
• 所有测试用例的 $n$ 总和不超过 $3\times 10^5$，因此总复杂度 $O(3\times 10^5 \times 30)$，完全可行。

---

示例验证（以第一组数据为例）

$n=4, k=1, s=\text{BRBR}, a=[9,3,5,4]$

• 二分 $d=2$：检查

  • 重要格子（$a_i > 2$）：全部重要（9,3,5,4 都 >2）
  • 扫描：
    • i=1: $B$，上一个为 $R$，新区间，cnt=1，last=B
    • i=2: $R$，last=R
    • i=3: $B$，上一个为 $R$，新区间，cnt=2，last=B
    • i=4: $R$，last=R
  • cnt=2 > k=1，不可行

• 二分 $d=3$：重要格子（$a_i > 3$）：9,5,4（格子1,3,4）

  • 扫描：
    • i=1: $B$，last=R→新区间，cnt=1，last=B
    • i=3: $B$，上一个重要格子i=1是B，不新区间，last=B
    • i=4: $R$，last=R
  • cnt=1 ≤ k=1，可行

• 二分继续缩小，最终得到 $d=3$，与示例输出一致。

---

总结

本题的核心是：

1. 二分答案处理“最小值中的最大值”问题。
2. 将检查转化为：只考虑惩罚值大于当前阈值的格子，用贪心区间覆盖求最少涂蓝操作数。
3. 贪心扫描从左到右，每次遇到目标蓝色且上一个重要格子不是蓝色时，开启一个新操作。

这种“二分 + 贪心检查”是解决 min-max 类问题的经典模式。