小苯的魔法染色

[题目链接](https://www.nowcoder.com/practice/2e27509b990d4d02a70c0f208f078cdf)

思路

有一面长度为 的墙，用字符串表示，其中 W 代表白色，R 代表红色。小苯最多可以施放 次魔法，每次选择一个闭区间 ，将该区间内所有格子染成红色，且每次区间长度不超过 。求使整面墙都变成红色所需的最小 值。

二分答案

越大，每次操作能覆盖的范围越大，越容易在 次内完成染色。因此答案具有单调性：如果 可行，那么 也一定可行。这正是二分答案的经典特征。

我们对 进行二分，范围是 。对于每个候选的 值，检查能否用至多 次操作覆盖所有 W。

贪心验证

给定 ，如何判断是否可行？采用贪心策略：

  1. 预处理出所有 W 的位置，存入数组。
  2. 从左到右扫描，遇到第一个未被覆盖的 W 时，将区间的左端点放在这个 W 上，即覆盖 。
  3. 跳过所有被该区间覆盖的 W，继续处理下一个未覆盖的 W。
  4. 统计所需操作次数，若不超过 则可行。

贪心的正确性：每次操作的左端点越靠左，能覆盖到的右侧 W 越多，不会比其他策略更差。而把左端点恰好对齐到最左的未覆盖 W 上，保证了不浪费覆盖能力。

样例演示

输入 ，字符串 WRWWR：

W 的位置为 （0-indexed）。

  • 当 ：需要覆盖 ，共 3 次操作 ，不可行。
  • 当 ：第一次覆盖 （覆盖位置 0 的 W），第二次覆盖 （覆盖位置 2、3 的 W），共 2 次操作 ，可行。

因此最小 。

特殊情况

若字符串中没有 W，则无需操作，答案为 。

复杂度分析

  • 时间复杂度：，二分 轮，每轮贪心扫描 。
  • 空间复杂度：，存储 W 的位置数组。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    vector<int> ws;
    for(int i = 0; i < n; i++){
        if(s[i] == 'W') ws.push_back(i);
    }

    if(ws.empty()){
        cout << 0 << endl;
        return 0;
    }

    auto check = [&](int k) -> bool {
        int cnt = 0;
        int i = 0;
        while(i < (int)ws.size()){
            cnt++;
            if(cnt > m) return false;
            int right = ws[i] + k - 1;
            while(i < (int)ws.size() && ws[i] <= right) i++;
        }
        return true;
    };

    int lo = 1, hi = n;
    while(lo < hi){
        int mid = (lo + hi) / 2;
        if(check(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String s = br.readLine().trim();

        List<Integer> ws = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'W') ws.add(i);
        }

        if (ws.isEmpty()) {
            System.out.println(0);
            return;
        }

        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (check(ws, mid, m)) hi = mid;
            else lo = mid + 1;
        }
        System.out.println(lo);
    }

    static boolean check(List<Integer> ws, int k, int m) {
        int cnt = 0;
        int i = 0;
        while (i < ws.size()) {
            cnt++;
            if (cnt > m) return false;
            int right = ws.get(i) + k - 1;
            while (i < ws.size() && ws.get(i) <= right) i++;
        }
        return true;
    }
}