题解：P12350 「HCOI-R2」光影 最后更新于 2025-05-01 15:46:41

[题目传送门](https://www.luogu.com.cn/problem/P12350) # 思路 将字符串划分为块，筛选出可合并 $1$ 块的 $0$ 块，再利用贪心策略优先删除长度小的 $0$ 块，最终得到 $1$ 块的最小数量。 # AC Code ```cpp #include<bits/stdc++.h> using namespace std; struct Blk { char c; int cnt; }; int main() { int n,k; string s; cin>>n>>k>>s; vector<Blk> bs; Blk curBlk={s[0],1}; for(int i=1;i<n;++i) { if(s[i]==curBlk.c) curBlk.cnt++; else { bs.push_back(curBlk); curBlk.c=s[i]; curBlk.cnt=1; } } bs.push_back(curBlk); int m=0; for(const auto& b:bs) if(b.c=='1') m++; vector<int> zs; for(int i=0;i<bs.size();++i) if(bs[i].c=='0') if(i>0&&i<bs.size()-1&&bs[i-1].c=='1'&&bs[i+1].c=='1') zs.push_back(bs[i].cnt); sort(zs.begin(),zs.end()); int sum=0; int x=0; for(int z:zs) { if(sum+z<=k) { sum+=z; x++; } else break; } cout<<m-x; return 0; } ``` 勿抄代码！！！