自动搬运

查看原文

来自洛谷，原作者为

	_hud Hi

搬运于2025-08-24 23:14:51，当前版本为作者最后更新于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;
}