CF1066B 题解

· · 题解

看到其他题解都写的是一个贪心思路，那么我在这里提供一个新的贪心思路。

首先我来提供一组样例，

输入：

6 4
1 0 1 1 1 0

输出：

1

对于这个样例，容易看出，我们只需要选择第三个加热器就能使得整个屋子都被加热了，然后我们就可以想一个贪心策略，那就是先把所有加热器都打开，然后在从左到右依次判断这个加热器关闭后整个屋子是否依然被加热，如果依然被加热，则可以关掉这个加热器，反之则不能关掉这个加热器。

那么这个时候肯定有人就要问了，正确性呢？

由于判断了整个屋子是否依然被加热的情况，因此若可以使整个屋子被加热，则最后屋子的状态一定均是被加热的，而正因为加上了这个判断，因此选择的加热器也依然是最优的，因此这样贪心一定是正确的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1010],b[1010],sum,pd;
void init(long long l,long long r)
{
    pd=0;
    for(int i=l;i<=r;i++)
    {
        b[i]--;
        if(!b[i])
            pd=1;
    }
    if(pd)
    {
        for(int i=l;i<=r;i++)
            b[i]++;
        return ;
    }
    sum--;
}
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
int main()
{
    IOS;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==1)
        {
            sum++;
            for(int j=max(1ll,i-m+1);j<=min(n,i+m-1);j++)
                b[j]++;
        }
    }
    for(int i=1;i<=n;i++)
        if(!b[i])
        {
            cout<<-1;
            QwQ;
        }
    for(int i=1;i<=n;i++)
        if(a[i])
            init(max(1ll,i-m+1),min(n,i+m-1));
    cout<<sum;
    QwQ;
}