OK U! 题解

new_user_2 2023-12-04 22:24:22 2023-12-04 22:25:11

显而易见,删除操作只会在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;
}