CSP-J 入门级 · CSP 2020 入门级第一轮 第 20 题

2.

（最小区间覆盖）给出 $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)
     

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考贪心覆盖区间，先按左端点排序，再剔除被完全覆盖的无效区间，然后每次在能接上当前已覆盖右端点 r 的区间里选右端点最大的，不断推进直到覆盖 m。

最容易把排序条件搞反，按右端点排就全错；去重时只比左端点或只比右端点都不行，必须判断后一个区间是否被前一个完全包含（即左端点更大且右端点更小）；贪心选区间时漏了检查左端点是否≤r，导致选了接不上的区间；更新 r 时写成 max(r, A[q].a) 或只加一个数，没取到真正延伸最远的右端点；还有边界处 q+1<n 写漏，越界访问数组。

考点与思路：这是一道经典的最小区间覆盖贪心题。核心思想是：既然要覆盖 [0,m]，我们只需要关心“当前已经覆盖到了哪里”。假设当前覆盖到了位置 r（初始 r=0），那么下一步必须选一个左端点≤r 的区间，而且为了用最少的区间，我们当然要在所有满足条件的区间里挑右端点最大的那个，这样能一次把覆盖范围推得最远。重复这个过程直到 r≥m。程序里用冒泡排序实现排序，用一次扫描去重，再用 while 循环模拟贪心选择。下面逐空推导。

① 排序条件：贪心策略要求区间按左端点从小到大排，这样排序后，对于任意位置 i，A[i] 的左端点一定 ≤ A[i+1] 的左端点。冒泡排序的写法是外层 i 控制趟数，内层 j 从 1 开始往后比较，如果前面的比后面的大就需要交换。因此比较条件必须是 A[j].a > A[j-1].a，选 C。注意不要选成右端点比较，那样排出来的顺序对贪心毫无意义。

② 交换语句：冒泡排序在发现 A[j].a > A[j-1].a 时，要把 A[j] 和 A[j-1] 互换。代码里先保存 A[j] 到临时变量 t，然后 A[j]=A[j-1]，再把 t 赋给 A[j-1]。对应选项 D：A[j]=A[j-1]; A[j-1]=t;。其他选项要么把 t 放错位置，要么交换顺序反了，都会把排序结果搞乱。

③ 去重逻辑：排序完成后，如果某个区间完全落在前一个区间内部（即它的左端点更大且右端点更小），这个区间对覆盖没有贡献，可以直接删掉。代码用变量 p 作为“有效区间”的末尾索引，初始 p=1 表示第一个区间 A[0] 肯定保留。遍历 i 从 1 到 n-1，如果 A[i].b > A[p-1].b，说明这个区间比当前最后一个有效区间延伸得更远，那就保留它，把它挪到 p 位置并 p++；否则说明它被前面的区间完全覆盖了，直接跳过。因此条件应为 A[i].b > A[p-1].b，选 A。这里的关键是 p-1 指向的是当前最后一个有效区间的右端点，而不是 i-1，千万别写成 A[i].b > A[i-1].b，那样会误删很多本来有用的区间。

④ 贪心选择区间：当前已覆盖到 r，我们需要在剩余区间里找到左端点≤r 且右端点最大的那个。代码里用 q 指向当前候选区间（初始 q=0，指向第一个有效区间）。外层 while(r<m) 保证还没覆盖完。内层 while 要不断往后推 q，只要 q+1<n 且 A[q+1].a≤r，就说明下一个区间也能接上，就 q++。注意这里一定要用 q+1<n，因为 q 本身是当前选中的区间，我们想往后看的是 q+1。选 A 正确。如果写成 q<n 就会多访问一次 A[q].a，逻辑混乱；如果条件里用 b 比较就完全错了，因为我们要的是左端点≤r 才能接上。

⑤ 更新覆盖右端点：内层循环结束后，q 指向的就是所有能接上 r 的区间里左端点最小的那个（其实就是第一个满足条件的），而由于数组已经按左端点排序，q 后面的区间左端点都≥A[q].a，所以 A[q] 就是当前能接上的区间中右端点最大的（因为如果有更右的，它一定也在 q 后面，但 q 已经推到最前了，实际上这里逻辑是：q 指向第一个满足 a≤r 的区间，而由于我们之前去重保留了右端点递增的区间，所以 A[q].b 就是当前能接上的最大右端点）。因此要把 r 更新为 max(r, A[q].b)。选 B。千万别写成 A[q+1].b，那会越界或者选错区间；写成 A[q].a 就更离谱了。

整体流程复盘：先按左端点冒泡排序，再去掉被完全覆盖的区间，然后循环：只要 r<m，就往后找所有左端点≤r 的区间，取第一个（也就是右端点最大的），用它的右端点扩展 r，计数加一。这样保证每一步都选了最优的区间，最终得到最少个数。

易错点再强调：排序条件一定要是左端点；去重时比较的是当前最后一个有效区间的右端点 A[p-1].b，不是 A[i-1].b；贪心内层 while 一定要用 q+1<n，否则多读一次；更新 r 一定要用 A[q].b。这些细节一旦写错，整个算法就崩了。

考频与趋势：从题库数据看，模拟类题目共 178 题，其中 CSP 入门级占了 134 题，占比最高，说明入门级非常偏爱这类“补全程序 + 基础算法”的题型。贪心算法本身在题库里共 71 题，CSP 入门级有 12 题，GESP 五级有 25 题，可见贪心是入门到中级的高频考点。排序基础题 249 题，CSP 入门级 44 题，GESP 四级 39 题，说明排序也是必考基本功。历年趋势上，2026 年模拟题暴增到 38 题，贪心题也冲到 24 题，排序题更是 50 题，整体呈现“基础算法题在入门级和 GESP 中持续高占比，且近年数量明显上升”的特点。

预测：基于上述高频分布和近年增长趋势，未来 CSP 入门级和 GESP 四级、五级继续大概率会出现类似“补全程序 + 贪心/排序/模拟”的组合题，难度可能维持在“读懂题意 + 关键条件填空”的水平，不太会突然跳到复杂 DP 或图论。若出题人想增加区分度，可能会在贪心条件里埋更隐蔽的坑（比如区间重叠判断、去重逻辑更复杂），但核心思想不会变。暂无足够依据预测具体年份的题目形式，只能建议同学们把冒泡排序、去重扫描、贪心区间选择这三块练到肌肉记忆。