题解：P12350 「HCOI-R2」光影

_hud · 2025-05-03 14:05:46 · 题解

题解：P12350 「HCOI-R2」光影

思路

题目要求通过删除 k 个 0，使得剩余的 1 块数最少。故不难想到贪心。显然，若两个 1 块之间有 m 个 0，删除其中 m 个 0 即可合并这两个块。为了最小化块数，应优先删除间隔最小的两个 1 块中间的 0 ，因为它们能用更少的删除次数合并更多块。不难得出这个贪心策略是成立的。

实现就不细讲了，具体可以看代码。

代码

#include <bits/stdc++.h>
using namespace std;
int n, k, sep[10000010], cnt = 1, ans;
string s;
signed main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> k >> s;
    int tmp = 0, i = 0;
    // 去除前导零，因为其对答案没有贡献
    for(; i < n; i++)
        if(s[i] == '1' && s[i+1] != '1') break;
    for(i++; i < n; i++)
        if(s[i] == '1') {
            if(s[i-1] != '1') // 前一个字符是0，说明前面是一个完整的间隔，记录
                sep[cnt++] = tmp, tmp = 0;
        } else tmp++;
    sort(sep+1, sep+cnt);
    // 计算初始块数
    for(int i = 0; i < n; i++) 
        if(s[i] == '1' && s[i-1] != '1')
            ans++;
    if(ans == 0) { // 特判
        cout<< 0 << '\n'; 
        return 0; 
    }
    for(int i = 1; i < cnt; i++)
        if(k >= sep[i]) // 当前间隔足够删除
            ans--, k -= sep[i];
        else break; // 否则不够，退出
    cout << ans;
    return 0;
}