CSPJ2020 完善程序2
(最小区间覆盖)给出n个区间，第i个区间的左右端点是【ai,bi】，现在要在这些区间中选出若干个，使得区间[0, m]被所选区间的并覆盖(即每一个0<=i<=m都在某个所选的区间中)。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数n和m(1<=n<=5000,1<=m<=10^9)
接下来n行，每行两个整数ai,bi(0<=ai,bi<=m)。
提示:使用贪心法解决这个问题。先用θ(n^2)的时间复杂度排序，然后贪心选择这些区间
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment {
int a, b;
} A[MAXN];
void sort() { // 排序
for(int i=0; i<n; i++)
for(int j=1; j<n; j++)
if (①) {
segment t = A[j];
②
}
}
int main() {
cin>>n>>m;
for(int i=0; i<n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p=1;
for(int i=1; i<n; i++)
if (③)
A[p++] = A[i];
n=p;
int ans=0,r=0;
int q=0;
while (r < m) {
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
阅读代码，填空
①处应填()
A[j].b < A[j-1].b
A[j].a < A[j-1].a
A[j].a > A[j-1].a
A[j].b > A[j-1].b
②处应填()
A[j+1]=A[j]; A[j]=t;
A[j-1]=A[j]; A[j]=t;
A[j]=A[j+1];A[j+1]=t;
A[j]=A[j-1];A[j-1]=t;
③处应填()
A[i].b > A[p-1].b
A[i].b < A[i-1].b
A[i].b > A[i-1].b
A[i].b < A[p-1].b
④处应填()
q+1<n && A[q+1].b<=r
q+1<n && A[q+1].a<=r
q<n && A[q].a<=r
q<n && A[q].b<=r
⑤处应填()
r = max(r, A[q+1].b)
r = max(r, A[q].b)
r = max(r, A[q+1].a)
q++
发表评论