显而易见,删除操作只会在O......U的情况下对最终的OU数量有贡献。其中......表示若干个K。
那么我们只需要统计每一段O与U之间的K的数量,从小到大排序之后判断即可。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
string s;
cin >> n >> k >> s;
int p = -1;
multiset<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == 'U' && p != -1) {
st.insert(p);
p = -1;
}
if (s[i] == 'O')
p = 0;
if (s[i] == 'K' && p != -1)
p++;
}
int sum = 0, ans = 0;
for (auto x : st) {
sum += x;
if (sum > k)
break;
ans++;
}
cout << ans << endl;
}