题目链接

小茶的魔法染色

题目描述

小红有一堵长度为 的墙，由 'W' (白色) 和 'R' (红色) 组成。她想将整面墙染成红色。

魔法师小茶可以施法，一次施法可以选择一个闭区间 并将其全部染红。他最多可以施法 次，且每次施法的区间长度 不得超过一个最大值 。

你需要找到能完成任务的最小的 。

解题思路

这是一个典型的“求解最小的可能的最大值”问题，非常适合使用二分答案。

1. 预处理

首先，我们应该处理一个特殊情况：如果墙壁初始状态已经是全红色（即字符串中不包含 'W'），那么根本不需要施法。在这种情况下，对施法长度 没有任何要求，最小的 可以认为是 。因此，我们先检查这一点，如果是，直接输出 。

如果墙壁上至少有一块是白色的，我们才需要进行后续的二分查找。此时，最小的 必然是一个正整数。

2. 单调性分析

我们所求的答案是 ，即允许的最大施法长度。

  • 如果一个长度上界 是可行的（即用不超过 次、长度不超过 的施法就能染红整面墙），那么任何比 更大的长度上界（如 ）也一定是可行的。因为我们拥有的能力（单次施法长度）变强了，原有的可行方案依然有效。
  • 反之，如果长度上界 不可行，那么任何比 更小的长度上界也必然不可行。

这种单调性是使用二分答案的基础。我们可以将求解问题转化为一个判定问题。

3. 二分答案框架

我们在可能的答案范围 内对 进行二分查找。

  • check(L) 函数： 二分答案的核心是编写一个 check(L) 函数，它的作用是判定：“当单次施法长度上限为 时，我们是否能用不超过 次的施法完成任务？”

    要回答这个问题，我们可以采用贪心策略。为了尽可能减少施法次数，每一次施法都应该尽可能地高效。

    • 贪心策略：我们从左到右遍历墙壁。当遇到第一个白色格子 'W' 时，我们必须施法来覆盖它。为了让这次施法覆盖掉尽可能多的（潜在的）白色格子，最优的选择就是从当前位置开始，施放一个长度为 的法术。

    • check(L) 的实现：

      1. 初始化已用施法次数 。
      2. 用一个指针 从 开始扫描墙壁。
      3. 当 时：
        • 如果 是 'R'，则该处已染红，直接跳过，i++。
        • 如果 是 'W'，则必须施法。 增加 1，然后指针 向前跳跃 的长度（i += L），代表这个区间已被覆盖。
      4. 遍历结束后，如果 ，说明在长度限制为 的情况下，任务是可行的，返回 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 函数需要对字符串进行一次贪心扫描，时间复杂度为 。如果墙壁全红，则复杂度为 用于检查字符串。
  • 空间复杂度：，用于存储输入的字符串。