P12350 光影题解

## 思路

考虑贪心。

很显然的是：设 $\phi$ 为 $\texttt{\dots 1}\overlinesegment{\texttt{0\dots 0}}\texttt{1\dots}$ 中用线段标注出的一段，则把 $\phi$ 删除后，用 $\texttt{1}$ 连成的块的数量会减一。

更显然的是：如果同时有 $\phi_1$ 和 $\phi_2$，且 $\mid\phi_1\mid\lt\mid\phi_2\mid$，则删除 $\phi_1$ 比删除 $\phi_2$ 更优。

那我们可以每次删除最短的 $\phi$ 并更新 $\text{ans}$ 与 $k$ 直到 $k$ “用光”。

使用优先队列存储 $\mid\phi\mid$，注意特判全 $\texttt{0}$ 即可。

## 代码

``` cpp
#include <bits/stdc++.h>
typedef long long ll;
#define one(x) ((ll)(1e##x))
using namespace std;
typedef pair<int, int> pii;

int n, k;

string s;

int las(-2);

priority_queue<int, vector<int>, greater<int> > dis;

int ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>s;
    for(int i(0); i<n; i++) {
        if(s[i]=='1') {
            if(las>=0 && las!=i-1) dis.push(i-las-1);
            las=i;
        }
    }
    if(dis.empty() && s.find("1")==string::npos) {
        cout<<0<<"\n";
        return 0;
    }
    ans=dis.size()+1;
    while(dis.size()) {
        k-=dis.top();
        dis.pop();
        if(k<0) break;
        ans--;
    }
    cout<<ans;
    return 0;
}
```