CSP 2020 入门组第一轮 第20题
【题目】
（最小区间覆盖）给出 n 个区间，第 i 个区间的左右端点是 \([a_i,b_i]\) 。现在要在这些区间中选出若干个，使得区间 \([0,m]\) 被所选区间的并覆盖（即每一个 \(0\leq{i}\leq{m}\) 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m （ \(1\leq{n}\leq5000, 1\leq{m}\leq{10^9}\) ） 接下来 n 行，每行两个整数 \(a_i\)，\(b_i\)（ \(0\leq{a_i,b_i}\leq{m}\) ）。
提示：使用贪心法解决这个问题。 先用 \(O({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;
}
1) ①处应填（ B ）
2) ②处应填（ D ）
3) ③处应填（ A ）
4) ④处应填（ A ）
5) ⑤处应填（ B ）
1. A. A[j].b>A[j-1].b B. A[j].a<A[j-1].a C. A[j].a>A[j-1].a D. A[j].b<A[j-1].b 2. A. A[j+1]=A[j];A[j]=t; B. A[j-1]=A[j];A[j]=t; C. A[j]=A[j+1];A[j+1]=t; D. A[j]=A[j-1];A[j-1]=t; 3. A. A[i].b>A[p-1].b B. A[i].b<A[i-1].b C. A[i].b>A[i-1].b D. A[i].b<A[p-1].b 4. A. q+1<n&&A[q+1].a<=r B. q+1<n&&A[q+1].b<=r C. q<n&&A[q].a<=r D. q<n&&A[q].b<=r 5. A. r=max(r,A[q+1].b) B. r=max(r,A[q].b) C. r=max(r,A[q+1].a) D. q++
【解析】
1. 按照 a 的大小升序排序，也就是保证：A[j-1].a <= A[j].a ，所以：
if(A[j-1].a > A[j].a) swap(A[j-1], A[j]);
2. 交换2个数据的方式：
int t = a;
a = b;
b = t;//上一个的结束就是下一个的开头
3. 将下一个区间放入，但是放入的要求是：A[i].b 大于已放入的最右边，也就是：
A[i].b>A[p-1].b
4. 区间个数肯定不能超过 n，并且即将放入的模块的右区间的值一定要完成重合或者连接，不能出现空格现象，所以：
q+1<n&&A[q+1].a<=r
5. 最后对右边区间取最大值，表示已经覆盖到某个点了：
r=max(r,A[q].b)