【GESP】C++五级练习题 luogu-P2242 公路维修问题
GESP C++ 五级练习题，贪心思想考点。题目难度⭐⭐★☆☆，适合五级入门练习，洛谷难度等级普及-。
luogu-P2242 公路维修问题
题目要求
题目描述
由于长期没有得到维修，A 国的高速公路上出现了 $n$ 个坑。为了尽快填补好这 $n$ 个坑，A 国决定对 $m$ 处地段采取交通管制。为了求解方便，假设 A 国的高速公路只有一条，而且是笔直的。现在给出 $n$ 个坑的位置，请你计算，最少要对多远的路段实施交通管制？
输入格式
输入数据共两行，第一行为两个正整数 $n, m(2 \le m \le n \le 15000)$。
第二行给出了 $n$ 个坑的坐标（坐标值均在长整范围内，按从小到大的顺序给出，且不会有两个点坐标相同）。
输出格式
仅一行，为最小长度和。
输入输出样例 #1
输入 #1
1
2
18 4
3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43
输出 #1
1
25
说明/提示
【样例说明】
交通管制的地段分别为：$3-8, 14-21, 25-31, 40-43$。
题目分析
这道题目的核心是贪心算法的应用。我们需要在 $n$ 个坑的位置中，选择最多 $m$ 个连续的区间来覆盖所有坑，使得区间的总长度最小。
1. 问题建模
首先，我们可以考虑两种极端情况：
- 最少分段：如果我们只用 $1$ 个区间覆盖所有坑，那么这个区间的起点必须是第一个坑的位置 $a[0]$，终点是最后一个坑的位置 $a[n-1]$。此时的总长度为 $L_{total} = a[n-1] - a[0] + 1$。
- 最多分段：如果我们用 $n$ 个区间，每个区间只覆盖一个坑，那么总长度就是 $n$（每个坑长度为 1）。
题目允许我们最多使用 $m$ 个区间。这就意味着，我们可以在初始的“1 个大区间”基础上，进行 $m-1$ 次“断开”操作。
2. 贪心策略
每“断开”一次，就相当于在某两个相邻的坑之间不进行管制（即不修路）。
假设我们在相邻的坑 $a[i]$ 和 $a[i+1]$ 之间断开，那么中间这段“空白区域”就不需要计入总长度。
这段空白区域的长度（即节省下来的长度）是：
\[\text{Saved} = (a[i+1] - a[i]) - 1\]或者简单理解为，两个坑的坐标差值 $gap = a[i+1] - a[i]$ 越大，如果不连接它们，节省的成本就越多。为了使最终的总长度最小，我们需要尽可能地多节省长度。
贪心策略：在所有相邻坑的间距中，选择最大的 $m-1$ 个间距进行断开。
3. 算法步骤
- 读取输入：读取 $n$ 和 $m$，以及 $n$ 个坑的坐标数组 $a$。
- 计算间距：遍历数组 $a$，计算所有相邻坑之间的距离 $sub[i] = a[i] - a[i-1]$，存入数组
sub。 - 排序：对
sub数组进行从大到小排序（或者从小到大排序后从后往前取）。 - 计算初始长度：假设只有一段，长度为 $ans = a[n-1] - a[0] + 1$。
- 减去最大间隔：从
sub中取出最大的 $m-1$ 个间隔值，从 $ans$ 中减去。- 注意细节：每减去一个间隔 $gap$，实际上是将一段分成了两段，中间空出了 $gap-1$ 的距离。
- 代码实现技巧：可以直接从 $ans$ 中减去 $gap$ 值，但因为多了一次分段（增加了一个新的闭区间端点），每减去一个 $gap$ 需要在结果上 $+1$。
- 或者理解为：$ans \leftarrow ans - (gap - 1)$。
- 代码中采用了统一处理：先减去所有 $gap$，最后统一加上 $m-1$。
4. 模拟演示
以样例输入为例： $n=18, m=4$。 坑坐标：3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43。
- 计算相邻间距：
- $4-3=1$
- $6-4=2$
- $8-6=2$
- $14-8=\mathbf{6}$
- $15-14=1$, …, $21-17=\mathbf{4}$
- $25-21=\mathbf{4}$, …, $30-27=3$
- $40-31=\mathbf{9}$
- … (其余均为 1 或小的数)
- 排序后的最大间距（前 $m-1=3$ 个）：
- $9$ (31 到 40 之间)
- $6$ (8 到 14 之间)
- $4$ (21 到 25 之间，或者 25 到 21 之间，取大的即可)
- 计算结果：
- 初始全覆盖长度：$43 - 3 + 1 = 41$
- 减去最大的 3 个间距：$41 - 9 - 6 - 4 = 22$
- 修正分段带来的端点计数：$22 + (4 - 1) = 25$
- 最终结果：25
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* P2242 公路维修问题
*
* 贪心策略：
* 1. 如果所有坑都连起来修，总长度是 a[n-1] - a[0] + 1。
* 2. 我们可以分m段修，意味着可以断开m-1个连接处（即减去m-1个间隔）。
* 3. 为了使总长度最小，应该尽可能减去最大的间隔。
* 4. 所以我们将相邻坑的距离算出并排序，减去最大的 m-1 个间隔即可。
*/
#include <algorithm>
#include <iostream>
int a[15005]; // 存储 n 个坑的位置
int sub[15005]; // 存储相邻坑之间的距离
int main() {
int n, m;
std::cin >> n >> m;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
// 特殊情况：如果坑的数量等于路段数，每个坑单独修，总长度为 n
if (n == m) {
std::cout << n << std::endl;
return 0;
}
// 计算相邻坑之间的距离
for (int i = 1; i < n; i++) {
sub[i] = a[i] - a[i - 1];
}
// 对距离进行从小到大排序
std::sort(sub + 1, sub + n);
// 初始总长度：将所有坑看作一段时的长度
int ans = a[n - 1] - a[0] + 1;
// 贪心：减去 m-1 个最大的间隔
// 排序后 sub[n-1] 是最大的，sub[n-2] 次之...
for (int i = 0; i < m - 1; i++) {
ans -= sub[n - 1 - i];
}
// ans 减去的是间隔的数值 (a[i+1] - a[i])。
// 每断开一个间隔，这就变成了两段。
// 实际上每多一段，因为端点的包含关系，总长度相比单纯减去间隔数值要多 1。
// 或者可以理解为：
// 每减去一个间隔 gap，节省的长度是 gap - 1。
// 代码中是先减去 gap，最后再统一把每段多减去的 1 加回来。
// 共断开 m-1 次，所以最后加 m-1。
std::cout << ans + m - 1 << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
