小苯的魔法染色

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt(),m=in.nextInt();
        TreeSet<Integer> set=new TreeSet<>();
        in.nextLine();
        String wall=in.nextLine();
        for(int i=0;i<n;i++) {
            if(wall.charAt(i)=='W') set.add(i);
        }
        if(set.ceiling(0)==null) {
            System.out.print(0);
            return;
        }
        int left=-1,right=n+1;
        while(left+1<right) {
            int mid=(left+right)/2;
            if(check(set,mid,m)) right=mid;
            else left=mid;
        }
        System.out.print(right);
    }
    public static boolean check(TreeSet<Integer> set,int k,int m) {
        int idx=set.ceiling(0);
        Integer temp;
        for(int i=0;i<m;i++) {
            idx+=k;
            if((temp=set.ceiling(idx))==null) return true;
            idx=temp;
        }
        return false;
    }
}

#include <cstddef>
#include <iostream>
using namespace std;

bool check(string& s, int k, int m, int n) {
    for (int i = 0; i < n; i++) {
        if (s[i] == 'W') {
            m--;
            // 上面i++还会有 + 1操作
            i += k - 1;
        }
        if (m < 0) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int left = 0, right = n;
    int ans = right;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(s, mid, m, n)) {
            ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

#include<bits/stdc++.h>
#include <iterator>
using namespace std;
#define int long long
#define endl '\n'
#define N 105

//k要最小，必定是施法m次
//二分的x是区间长度，check内部，是W的话需要染色，染完就跳过X个继续遍历
int c[N];
int n,m;
string s;
bool check(int x){
    int cnt=0;
    for(int i=0;i<s.size();){
        // cout<<"i"<<" "<<i<<endl;
        if(s[i]=='W'){
            i+=x;
            cnt++;
        }
        else 
            i++;
    }
    return cnt<=m;
}
void solve() {
    cin>>n>>m;
    cin>>s;
    int l=0,r=2*n;
    //判断是不是全是R
    int f=0;
    for(int i=0;i<s.size();i++)
        if(s[i]=='W')
            f=1;
    if(f==0){
        cout<<0<<endl;
        return ;
    }
    //现在x肯定是不为0
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else 
            l=mid;
    }
    cout<<r<<endl;
    return ;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    while (T--)
        solve();
    return 0;
}

import java.util.*;

public class Main {
    // 判断每次施法的区间长度为k是否可行
    private static boolean canCover(List<Integer> whitePos, int k, int m) {
        int cnt = 0, pos = 0, size = whitePos.size();
        while(pos < size) {
            cnt++;
            if(cnt > m) {
                return false;
            }
            int start = whitePos.get(pos);
            int maxReach = start + k - 1;
            // 二分查找whitePos 找到最后一个不超过maxReach的位置
            int left = pos, right = size - 1;
            int res = pos;
            while(left <= right) {
                int mid = right + (left - right >> 1);
                if(whitePos.get(mid) <= maxReach) {
                    res = mid;
                    left = mid + 1;
                } else {
                    right = mid -1;
                }
            }
            pos = res + 1;
        }
        return cnt <= m;
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        char[] wall = in.next().toCharArray();
        int ans = 0;
        List<Integer> whitePos = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            if(wall[i] == 'W') {
                whitePos.add(i);
            }
        }

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

        int left = 1, right = n;
        while(left <= right) {
            int mid = right + (left -right >> 1);
            if(canCover(whitePos, mid, m)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

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.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        for(int k=1;k<=n;k++){
            int tmp = m;
            for(int i=0;i<n;i++){
                char ch = str.charAt(i);
                if(ch == 'W'){
                    if(tmp == 0){
                        break;
                    }
                    tmp--;
                    i = i+k-1;
                }
                if(i >= n-1){
                    if(tmp == m) k = 0;
                    System.out.println(k);
                    return;
                }
            }
        }
    }
}

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;
    }
}

//事实上这种二分题有个小技巧 额外定义一个res用于储存符合条件的结果
//这样就不用纠结是取l还是r了
//由于该种条件已经被res保存 l可以无脑++ r可以无脑-- 去探索其他可能性
//符合条件就更新res 不符合就不更新res 这种限制下结束二分输出的结果一定是符合条件的res
//几乎适用于所有二分

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//数组长度
        int MaxMagicCount = in.nextInt();
        in.nextLine();
        String s = in.nextLine();
        if (s.contains("W")) {//有白色才染色
            int l = 1;
            int r = (int) 1e6;
            int res = (int) 1e8;//随便定义一个都行
            while (l <= r) {
                boolean AllRed = true;//假设都可以染红
                int CurMagicCount = 0;
                int mid = l + (r - l) / 2;
                //从开头开始尝试染色
                for (int i = 0; i < n; i++) {
                    if (s.charAt(i) == 'W') {
                        //遇到白色使用能力 直接跳到施法后mid-1格 方便循环的i++后的下一个格子是没有检查过的
                        i = i + mid - 1;
                        CurMagicCount++;
                        if (CurMagicCount > MaxMagicCount) {
                            AllRed = false;//提前终止条件为超过最大次数
                            break;
                        }
                    }
                }
                if (AllRed) {
                    res = mid;//都红了说明是个可行解 存储
                    r = mid - 1;//尝试减小范围
                } else {
                    l = mid + 1;//不能全染得增大范围了
                }
            }
            System.out.println(res);
        } else {
            System.out.println(0);//没有白色不用染色了
        }
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt(), act = in.nextInt();
        char[] wall = in.next().toCharArray();
        int maxPW = 0;
        boolean flag = true;
        while (flag) {
            int life = act;
            int step = 0;
            while (step < len) {
                if ('W' == wall[step]) {
                    life--;
                    if (life < 0) {
                        maxPW++;
                        break;
                    }
                    step += maxPW;
                } else step++;
            }
            if(step >= len) flag = false;
        }
        System.out.println(maxPW);
    }
}

n, m = map(int, input().split())
wall = input()



def can_paint(k):
    count = 0
    i = 0
    while i < n:
        # 找到当前位置右侧最近的白色格子
        j = i
        while j <  n and wall[j] == 'R':
            j += 1
        if j == n:
            break
        end = min(j + k - 1, n - 1)
        i = end + 1
        count += 1
    return count <= m

# 因为最少要涂一块，所以left = 1
left, right = 1, n
while left < right:
    mid = (left + right) // 2
    if can_paint(mid):
        right = mid
    else:
        left = mid + 1

# 检查一下是不是真的不需要涂
wuhu = [char for char in wall if char == 'W']
if wuhu == []:
    print(0)
else:
    print(left)