题解 | 小苯的魔法染色

#include <bits/stdc++.h>
using namespace std;
 
const int N=2e5+5;
int n;
int m;
string s;

bool f(int x){
    int c=0;
    for(int i=0;i<n;i++){
        if(s[i]=='W'){
            c++;
            i+=x-1;
        }
        if(c>m) return false; //x为0时会死循环所以要剪枝
    }
    return c<=m;
}
int main() {
    cin>>n>>m;
    cin>>s;
    
    int l=0,r=n;
    int ans=n;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(f(mid)){
            ans=mid;
            r=mid-1;
        } else{
            l=mid+1;
        }
    }
    cout<<ans;
}
// 64 位输出请用 printf("%lld")