题解 | #小苯的魔法染色#
小苯的魔法染色
https://www.nowcoder.com/practice/2e27509b990d4d02a70c0f208f078cdf
题目链接
题目描述
小红有一堵长度为 的墙，由 'W' (白色) 和 'R' (红色) 组成。她想将整面墙染成红色。
魔法师小茶可以施法，一次施法可以选择一个闭区间 并将其全部染红。他最多可以施法
次，且每次施法的区间长度
不得超过一个最大值
。
你需要找到能完成任务的最小的 。
解题思路
这是一个典型的“求解最小的可能的最大值”问题，非常适合使用二分答案。
1. 预处理
首先，我们应该处理一个特殊情况：如果墙壁初始状态已经是全红色（即字符串中不包含 'W'），那么根本不需要施法。在这种情况下，对施法长度 没有任何要求，最小的
可以认为是
。因此，我们先检查这一点，如果是，直接输出
。
如果墙壁上至少有一块是白色的，我们才需要进行后续的二分查找。此时，最小的 必然是一个正整数。
2. 单调性分析
我们所求的答案是 ，即允许的最大施法长度。
- 如果一个长度上界
是可行的（即用不超过
次、长度不超过
）也一定是可行的。因为我们拥有的能力（单次施法长度）变强了，原有的可行方案依然有效。
- 反之，如果长度上界
这种单调性是使用二分答案的基础。我们可以将求解问题转化为一个判定问题。
3. 二分答案框架
我们在可能的答案范围 内对
进行二分查找。
-
check(L)函数： 二分答案的核心是编写一个check(L)函数，它的作用是判定：“当单次施法长度上限为要回答这个问题，我们可以采用贪心策略。为了尽可能减少施法次数，每一次施法都应该尽可能地高效。
-
贪心策略：我们从左到右遍历墙壁。当遇到第一个白色格子 'W' 时，我们必须施法来覆盖它。为了让这次施法覆盖掉尽可能多的（潜在的）白色格子，最优的选择就是从当前位置开始，施放一个长度为
-
check(L)的实现：- 初始化已用施法次数
。
- 用一个指针
从
开始扫描墙壁。
- 当
时：
- 如果
是 'R'，则该处已染红，直接跳过，
i++。 - 如果
增加 1，然后指针
i += L），代表这个区间已被覆盖。
- 如果
- 遍历结束后，如果
，说明在长度限制为
true。否则返回false。
- 初始化已用施法次数
-
-
二分过程：
- 设置二分区间
为
。
- 取中点
。如果
check(mid)为true，说明寻找更优解。如果为
false，说明寻找解。
- 设置二分区间
代码
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 检查最大长度为 k_val 时，是否能用不超过 m 次施法完成
bool check(int k_val, int n, int m, const string& s) {
int spells_used = 0;
int i = 0;
while (i < n) {
if (s[i] == 'R') {
i++;
} else { // s[i] == 'W'
spells_used++;
i += k_val;
}
}
return spells_used <= m;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
string s;
cin >> s;
// 预处理：如果墙壁已经是全红色，答案为0
if (s.find('W') == string::npos) {
cout << 0 << endl;
return 0;
}
int left = 1, right = n;
int ans = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid, n, m, s)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << endl;
return 0;
}
import java.util.Scanner;
public class Main {
// 检查最大长度为 kVal 时，是否能用不超过 m 次施法完成
private static boolean check(int kVal, int n, int m, String s) {
int spellsUsed = 0;
int i = 0;
while (i < n) {
if (s.charAt(i) == 'R') {
i++;
} else { // s.charAt(i) == 'W'
spellsUsed++;
i += kVal;
}
}
return spellsUsed <= m;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
String s = sc.next();
// 预处理：如果墙壁已经是全红色，答案为0
if (!s.contains("W")) {
System.out.println(0);
return;
}
int left = 1, right = n;
int ans = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid, n, m, s)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
System.out.println(ans);
}
}
def check(k_val, n, m, s):
spells_used = 0
i = 0
while i < n:
if s[i] == 'R':
i += 1
else: # s[i] == 'W'
spells_used += 1
i += k_val
return spells_used <= m
def main():
n, m = map(int, input().split())
s = input().strip()
# 预处理：如果墙壁已经是全红色，答案为0
if 'W' not in s:
print(0)
return
left, right = 1, n
ans = n
while left <= right:
mid = (left + right) // 2
if check(mid, n, m, s):
ans = mid
right = mid - 1
else:
left = mid + 1
print(ans)
if __name__ == "__main__":
main()
算法及复杂度
- 算法：二分答案 + 贪心。
- 时间复杂度：
。在最坏情况下（墙壁不为全红），二分查找需要进行
次迭代。在每次迭代中，
check函数需要对字符串进行一次贪心扫描，时间复杂度为。如果墙壁全红，则复杂度为
- 空间复杂度：
