贪心、区间覆盖问题
贪心
题目描述:
题目等价于给定一些区间,求覆盖总区间的最小区间数。
解题思路:
将所有区间按照左端点从小到大排序(本题已经满足,不需要排序),记录一个maxr表示当前已经覆盖的最远右端点。
如果我们要选择一个区间来增加maxr的值,那么这个区间的左端点必须不大于maxr+1,否则会出现断点。
在所有合法的这些区间里选择一个右端点最远的来更新maxr。如果没有合法区间直接返回-1.
最后判断maxr是否大于等于n即可。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
PII q[N];
int n, ri, a, cnt;
int main(){
cin >> n >> ri;
for(int i = 1; i <= n; ++i){
cin >> a;
if(a == 1) q[++cnt] = {i-ri+1, i+ri-1};
}
if(!cnt){
cout << -1;
return 0;
}
int i = 1, res = 0, maxr = 0;
bool flag = true;
while(i <= cnt){
int mr = -1, id = -1;
for(int k = i; k <= cnt && q[k].first <= maxr + 1; ++k){
if(q[k].second > mr){
mr = q[k].second, id = k;
}
}
if(mr != -1){
maxr = mr, res++, i = id+1;;
if(maxr >= n)break;
}
else{
flag = false;
break;
}
}
if(flag && maxr >= n)cout << res;
else cout << -1;
return 0;
}
哦 这题的区间本来就是有序的 根本不需要排序