CSP-J 2020 第一轮 第 40 题：最小区间覆盖：②处应填

题目

（最小区间覆盖）给出 $n$ 个区间，第 $i$ 个区间的左右端点是 $[a_i,b_i]$。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $0\leq i\leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le 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;
   }

②处应填（ ）

选项

• 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;

答案

D

题解

选 D：A[j]=A[j-1];A[j-1]=t;

这里使用冒泡排序，需要交换相邻的 A[j-1] 和 A[j]。前面已经用 t 保存了 A[j]，所以完整交换过程是：

``cpp segment t = A[j]; // 暂存 A[j] A[j] = A[j-1]; // 把前一个元素放到当前位置 A[j-1] = t; // 把原来的 A[j] 放到前一个位置 ``

其他选项为什么不对：

• A、C：访问 A[j+1]，当 j = n-1 时会超出有效区间。
• B：t 本来就等于 A[j]，这样会让两个位置都变成原来的 A[j]，没有完成交换。

这道题虽然背景是贪心算法，但 ②只考查借助临时变量交换两个元素。