CSP 2020 入门组第一轮 第20题:最小区间覆盖

2021年8月24日 | 分类: 【编程】

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)

参考:https://www.cnblogs.com/hellohebin/p/15110990.html