题解：P12350 「HCOI-R2」光影

HP_Serenity · 2025-04-30 21:53:10 · 题解

居然还能写题解。

要求删除 k 个 0 之后，让 1 的块数最少。

可以先记录所有 0 的位置，初始化 1 的块数。再确定 1 块之间 0 的数量，即合并这两个 1 块要删除 0 的个数。开始贪心，优先合并间隔 0 数量少的 1 块。

具体的体现可以看到代码：

#include <bits/stdc++.h>
using namespace std;
int n, k, z[10000005], m, g[10000005], cnt, lop = -1, res, used;
char s[10000005];
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    cin >> n >> k >> (s+1);
    // 记录 0 的位置
    m = 0;
    for(int i=1; i<=n; i++)
        if(s[i]=='0') z[++m] = i;
    // 计算 1 块之间的 0 的数量
    cnt = 0;
    for(int i=1; i<=n; i++) {
        if(s[i]=='1') {
            if(lop!=-1&&i>lop+1) g[cnt++] = i-lop-1;
            lop = i;
        }
    }
    // 初始 1 的块数计算
    for(int i=1; i<=n; ) {
        if(s[i]=='1') {
            res ++;
            while(i<=n&&s[i]=='1') i ++;
        } else i ++;
    }
    // 贪心合并 1 块
    sort(g, g+cnt);
    for(int i=0; i<cnt; i++) {
        if(used+g[i]<=k) {
            used += g[i];
            res --;
        } else break;
    }
    cout << res;
    return 0;
}