笔试练习3（彩笔般）

你有一个长度为 n 的字符串 a，由字符 'R'（红色）和 'W'（白色）组成。你可以最多进行 m 次操作，每次操作可以选择一个长度不超过 k 的区间 [l, r]，将其中所有格子染成 'R'。

你的目标是让整个墙变成全 'R'，并且希望找出最小的 k 值，使得在 m 次以内完成任务。

核心思想：二分答案 + 贪心

我们可以使用 二分查找 来找到最小的 k 值： 设定一个范围 [1, n]。 对于每一个中间值 mid，判断是否可以在 m 次内、每次操作长度不超过 mid 的情况下，把所有的 'W' 变成 'R'。

如果可以，则尝试更小的 k（缩小右边界）

否则，需要更大的 k（扩大左边界）

如何判断某个 k 是否可行？

采用贪心策略： 从前往后扫描字符串 当遇到一个 'W'，就以它为起点向右扩展最多 k 个位置，尽可能多地覆盖后面的 'W', 每次这样操作算一次施法,统计总共需要多少次操作,如果总操作次数 ≤ m，说明这个 k 是可行的。

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    String a = in.next();

    // 二分查找最小的 k
    int left = 1;
    int right = n;
    int answer = n;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (canPaint(a, n, m, mid)) {
            answer = mid;
            right = mid - 1; // 尝试更小的 k
        } else {
            left = mid + 1; // 需要更大的 k
        }
    }

    System.out.println(answer);
}

// 判断在最多 m 次、每次最多涂 k 个格子的情况下能否全部涂红
private static boolean canPaint(String a, int n, int m, int k) {
    int ops = 0;
    int i = 0;

    while (i < n) {
        if (a.charAt(i) == 'W') {
            // 施法一次，涂 k 个
            ops++;
            i += k; // 跳过这次施法影响的区域
        } else {
            i++;
        }
    }

    return ops <= m;
}

}

时间复杂度分析

二分查找：O(log n)

每次检查：O(n)

总体复杂度：O(n log n)