题解 | 小苯的魔法染色
小苯的魔法染色
https://www.nowcoder.com/practice/2e27509b990d4d02a70c0f208f078cdf
#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")
查看23道真题和解析