题解 | 小苯的魔法染色

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

public class Main {
    public static void main(String[] args) throws IOException {

        // 使用BufferedReader读取输入，使用PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取第一行输入，分割为字符串数组
        String[] strA = br.readLine().trim().split("\\s+");

        int n = Integer.parseInt(strA[0]);    // 获取字符串长度
        int m = Integer.parseInt(strA[1]);    // 获取操作次数

        char[] c = new char[n];               // 创建字符数组，虽然在此代码中未使用

        String s= br.readLine().trim();      // 待处理的字符串

        int low = 0,high = n;                // 二分查找的边界
        int ans = n;                          // 初始化答案为字符串长度

        // 执行二分查找
        while(low<=high){
            int mid = low +((high-low)>>1);   // 计算中间值，使用位运算优化替代除法

            // 检查中间值是否满足条件
            if(check(mid,n,m,s)){
                ans = mid;                     // 如果满足条件，更新答案
                high = mid-1;                // 尝试寻找更小的解
            }else{
                low = mid+1;                 // 如果不满足，尝试更大的值
            }
        }

        // 输出最终结果
        out.println(ans);

        // 刷新输出流，确保所有输出都被写入
        out.flush();
        // 关闭输出流，释放资源
        out.close();
        // 关闭输入流，释放资源
        br.close();
    }
    
    private static boolean check(int k,int n,int m,String s){
        // 如果k为0，检查字符串中是否不包含'W'
        if(k==0){
            return !s.contains("W");
        }

        int count = 0; // 记录操作次数
        // 遍历字符串
        for (int i=0;i<n;i++){
            // 如果当前字符是'W'，增加操作计数
            if(s.charAt(i)=='W'){
                count++;
                // 如果操作次数超过m，返回false
                if(count>m){
                    return false;
                }
                // 跳过接下来的k-1个字符
                i+=(k-1);
            }
        }

        // 检查总操作次数是否不超过m
        return count<=m;
    }
}