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)