贪心算法实战：GESP C++五级练习题洛谷P2242公路维修问题解析

题目要求

题目描述

由于长期没有得到维修，A 国的高速公路上出现了 n 个坑。为了尽快填补好这些坑，A 国决定对 m 处地段采取交通管制。为了求解方便，假设 A 国的高速公路只有一条，而且是笔直的。现在给出 n 个坑的位置，请你计算，最少要对多远的路段实施交通管制？

输入格式

输入数据共两行，第一行为两个正整数 n, m (1 ≤ m ≤ n ≤ 15000)。

第二行给出了 n 个坑的坐标（坐标值均在长整范围内，按从小到大的顺序给出，且不会有两个点坐标相同）。

输出格式

仅一行，为最小长度和。

输入输出样例 #1

输入 #1

18 4
3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

输出 #1

25

说明/提示

【样例说明】

交通管制的地段分别为：3-8， 14-17， 21-31， 40-43。

题目分析

这是一道典型的贪心算法问题。核心目标是在 n 个点（坑）中，选取 m 个连续区间进行覆盖，使得所有区间的总长度最小。

1. 问题建模与思路

我们可以从覆盖的极端情况来思考：

1. 最少分段（1段）：用一个超长区间覆盖所有坑，起点是第一个坑 a[0]，终点是最后一个坑 a[n-1]。总长度为 a[n-1] - a[0] + 1。
2. 最多分段（n段）：每个坑单独作为一个区间，总长度即为坑的数量 n。

题目允许我们使用最多 m 个区间。这意味着我们可以从“1个大区间”这个初始状态出发，进行 m-1 次“断开”操作。每次“断开”意味着我们在某两个相邻的坑之间不实施管制，从而将一个大区间分割成两个小区间。

2. 贪心策略推导

关键在于：在哪里断开收益最大？

假设我们在相邻的坑 a[i] 和 a[i+1] 之间断开。原来这段需要管制的长度为 a[i+1] - a[i] - 1（因为两个端点所在的坑本身必须被覆盖）。如果我们选择断开，这部分长度就可以从总长度中节省下来。

显然，a[i+1] - a[i] 的值越大，断开后节省的长度 (a[i+1] - a[i] - 1) 就越多。因此，为了最小化最终的总管制长度，我们应该优先在相邻坑间距最大的地方断开。

贪心策略：计算所有相邻坑的坐标差（间隔），然后选择其中最大的 m-1 个间隔进行断开。

3. 算法步骤与复杂度分析

这是一种非常高效的贪心策略，其时间复杂度主要取决于排序操作。对于这类在序列中选取最优子集的问题，掌握其思想是提升算法与数据结构能力的关键。

1. 输入：读取 n, m 以及 n 个有序的坑坐标。
2. 计算间隔：遍历坐标数组，计算 n-1 个相邻间隔 sub[i] = a[i] - a[i-1]。
3. 排序：将 sub 数组按降序（或升序后从后往前取）排序。
4. 计算初始总长：total = a[n-1] - a[0] + 1。
5. 应用贪心：从总长 total 中减去最大的 m-1 个间隔值 sub[i]。
6. 修正长度：每断开一次，相当于增加了一个独立的管制段。在计算上，直接从总长中减去间隔值 gap 会多减了 1（因为 gap 包含了前一段的终点和后一段的起点）。因此，最终结果需要加上 m-1，即 ans = total - sum(selected_gaps) + (m-1)。

算法复杂度：计算间隔为 O(n)，排序为 O(n log n)，整体复杂度为 O(n log n)，在给定数据范围内完全可行。

4. 模拟演示（以样例为例）

输入：n=18, m=4
坑坐标：3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

1. 计算相邻间隔（部分关键间隔）：

   • 3-4: 1
   • 6-8: 2
   • 8-14: 6
   • 17-21: 4
   • 21-25: 4
   • 31-40: 9
   • 其余多为 1。

2. 选择最大 m-1=3 个间隔：9 (31-40), 6 (8-14), 4 (选取一个，如21-25或17-21)。

3. 计算总长：

   • 初始总长 total = 43 - 3 + 1 = 41。
   • 减去最大间隔 41 - (9+6+4) = 22。
   • 加上段数修正 22 + (4-1) = 25。

最终结果与样例输出一致。

示例代码 (C++)

/**
 * P2242 公路维修问题 - 贪心解法
 * 策略：计算所有相邻坑的间距，减去最大的 (m-1) 个间距。
 */
#include <algorithm>
#include <iostream>

int a[15005];   // 存储坑的坐标
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;
    }

    // 1. 计算所有相邻坑的间距
    for (int i = 1; i < n; ++i) {
        sub[i] = a[i] - a[i - 1];
    }

    // 2. 对间距进行排序（默认升序）
    std::sort(sub + 1, sub + n);

    // 3. 计算初始总长度（全部连成一段）
    int total_length = a[n - 1] - a[0] + 1;

    // 4. 贪心：减去最大的 (m-1) 个间距
    // 升序排序后，最大的间距在数组末尾
    for (int i = 0; i < m - 1; ++i) {
        total_length -= sub[n - 1 - i];
    }

    // 5. 输出结果，加上 (m-1) 进行修正
    std::cout << total_length + m - 1 << std::endl;

    return 0;
}

---

在线评测：

• 本题（luogu-P2242）可在 洛谷 进行在线评测。
• 更多编程启蒙题目（bcqm- 系列）可在 编程启蒙题库 进行评测。