题解：P12350 「HCOI-R2」光影

Andy2011 · 2025-05-03 10:07:24 · 题解

P12350 「HCOI-R2」光影题解

思路

贪心。用一个 vector 记录 1 之间 0 的个数，从小到大排序，这样每次删除最少的 0，1 的块数自然最少。

坑点：如果全是 0 答案应该为 0。

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int l=0,r=s.length();
    while (s[l]=='0') l++; //去除前导零 
    while (s[r]=='0') r--; //去除后导零 
    if (l==r){ //坑点 
        cout<<0;
        return 0;
    }
    int cnt=0; //暂存连续0的个数 
    for (int i=l;i<=r;i++){
        if (s[i]=='0'){
            cnt++;
        }
        if (s[i]=='1'){
            if (cnt!=0){ //避免重复计算 
                v.push_back(cnt);
            }
            cnt=0;
        }
    }
    sort(v.begin(),v.end()); //从小到大排序 
    cnt=0; //cnt记录可以合并的1的块数 
    for (int i:v){
        if (k>=i){
            k-=i;
            cnt++;
        }
        else{
            break;
        }
    }
    cout<<v.size()+1-cnt; //0的块数+1就是1的块数 
    return 0;
}