区间排序加贪心
将区间计算出来 然后按左端点排序 然后用尽可能少的区间去覆盖全部区域
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010;
int a[N];
PII inter[N];
int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
int cnt = 0;
for(int i = 1; i <= n; i++){
if(a[i]) inter[cnt++] = {max(1, i - m + 1), i + m - 1};
}
sort(inter, inter + cnt);
if(cnt && inter[0].x <= 1){
int pos = 0, r = 0, res = 0;
for(int i = 1; i <= n; i++){
if(r < i){
int t = r;
while(pos < cnt && inter[pos].x <= t + 1){
r = max(r, inter[pos].y);
pos++;
}
if(r >= i){
res++;
}else{
break;
}
}
}
if(r >= n) cout << res << endl;
else cout << -1 << endl;
}else{
cout << -1 << endl;
}
return 0;
}