小苯的魔法染色

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

public class Main {
    static int n, m;
    static String s;
    public static void main(String[] args) {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] line = br.readLine().split("\\s+");
            n = Integer.parseInt(line[0]);
            m = Integer.parseInt(line[1]);
            s = br.readLine();
            boolean hasW = false;
            for (int i = 0; i < s.length(); ++i) {
                if (s.charAt(i) == 'W') {
                    hasW = true;
                    break;
                }
            }
            if (!hasW) {
                System.out.println(0);
                return;
            }
            int left = 1, right = n / m + (n % m) + 1;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                int i = 0, j = m;
                while (i < s.length()) {
                    if (s.charAt(i) == 'R') {
                        ++i;
                    } else {
                        i += mid;
                        --j;
                        if (j < 0) {
                            break;
                        }
                    }
                }
                if (j < 0) {
                    // k要开大一些
                    left = mid + 1;
                } else {
                    // k可以继续缩小
                    right = mid;
                }
            }
            System.out.println(left);
        } catch (IOException ie) {}
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), left = -1, right = n, last = n;
        String a = in.next();
        // 记录下一个白色块的位置，方便快速搜索
        int[] next = new int[n];
        for (int i=n-1; i>=0; i--) {
            if (a.charAt(i) == 'W') {
                last = i;
            }
            next[i] = last;
        }
        // 二分查找，区间左开右开(left, right)
        while (left + 1 < right) {
            int k = left + ((right - left) >> 1);
            if (check(next, k, n, m)) {
                right = k;
            } else {
                left = k;
            }
        }
        System.out.println(right);
    }

    private static boolean check(int[] next, int k, int n, int m) {
        int cnt = 0, index = 0;
        // next[index]表示从index开始的第一个W的位置
        // 每次染色表示位置+k，将所有包含W的染完的次数不超过m即可行
        while (index < n && next[index] < n) {
            // 找到下一个W的位置
            index = next[index];
            // 从当前的W块开始，染色k个块，继续检查后续
            index += k;
            // 染色次数超过m表示方案不可行
            cnt++;
            if (cnt > m) {
                return false;
            }
        }
        return true;
    }
}