题解：P12350 「HCOI-R2」光影

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> ones; // 存储所有 '1' 的位置

    // 读取输入并记录 '1' 的位置
    for (int i = 0; i < n; ++i) {
        char c;
        scanf(" %c", &c);
        if (c == '1') ones.push_back(i);
    }

    if (ones.empty()) { // 没有 '1' 的情况
        printf("0\n");
        return 0;
    }

    // 计算初始块数：连续的 '1' 视为一个块
    int initial_ones = 1;
    for (int i = 1; i < ones.size(); ++i) {
        if (ones[i] != ones[i-1] + 1) initial_ones++;
    }

    // 计算相邻块之间的间隙
    vector<int> gaps;
    int prev_end = ones[0]; // 前一个块的最后一个 '1' 的位置
    for (int i = 1; i < ones.size(); ++i) {
        if (ones[i] != ones[i-1] + 1) { // 发现新块
            int gap = ones[i] - prev_end - 1;
            if (gap > 0) gaps.push_back(gap);
            prev_end = ones[i];
        } else {
            prev_end = ones[i]; // 同一块内，更新末尾位置
        }
    }

    sort(gaps.begin(), gaps.end()); // 按间隙大小排序

    // 贪心合并：优先删除小间隙
    int merge_cnt = 0;
    for (int g : gaps) {
        if (k >= g) {
            k -= g;
            merge_cnt++;
        } else break;
    }

    printf("%d\n", initial_ones - merge_cnt);
    return 0;
}