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

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-21, 25-31, 40-43$。

题目分析

这道题目的核心是贪心算法的应用。我们需要在 $n$ 个坑的位置中，选择最多 $m$ 个连续的区间来覆盖所有坑，使得区间的总长度最小。

1. 问题建模

首先，我们可以考虑两种极端情况：

1. 最少分段：如果我们只用 $1$ 个区间覆盖所有坑，那么这个区间的起点必须是第一个坑的位置 $a[0]$，终点是最后一个坑的位置 $a[n-1]$。此时的总长度为 $L_{total} = a[n-1] - a[0] + 1$。
2. 最多分段：如果我们用 $n$ 个区间，每个区间只覆盖一个坑，那么总长度就是 $n$（每个坑长度为 1）。

题目允许我们最多使用 $m$ 个区间。这就意味着，我们可以在初始的“1 个大区间”基础上，进行 $m-1$ 次“断开”操作。

2. 贪心策略

每“断开”一次，就相当于在某两个相邻的坑之间不进行管制（即不修路）。

假设我们在相邻的坑 $a[i]$ 和 $a[i+1]$ 之间断开，那么中间这段“空白区域”就不需要计入总长度。

这段空白区域的长度（即节省下来的长度）是：

或者简单理解为，两个坑的坐标差值 $gap = a[i+1] - a[i]$ 越大，如果不连接它们，节省的成本就越多。为了使最终的总长度最小，我们需要尽可能地多节省长度。

贪心策略：在所有相邻坑的间距中，选择最大的 $m-1$ 个间距进行断开。

3. 算法步骤

1. 读取输入：读取 $n$ 和 $m$，以及 $n$ 个坑的坐标数组 $a$。
2. 计算间距：遍历数组 $a$，计算所有相邻坑之间的距离 $sub[i] = a[i] - a[i-1]$，存入数组 sub。
3. 排序：对 sub 数组进行从大到小排序（或者从小到大排序后从后往前取）。
4. 计算初始长度：假设只有一段，长度为 $ans = a[n-1] - a[0] + 1$。
5. 减去最大间隔：从 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。

1. 计算相邻间距：

   • $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 或小的数)

2. 排序后的最大间距（前 $m-1=3$ 个）：

   • $9$ (31 到 40 之间)
   • $6$ (8 到 14 之间)
   • $4$ (21 到 25 之间，或者 25 到 21 之间，取大的即可)

3. 计算结果：

   • 初始全覆盖长度：$43 - 3 + 1 = 41$
   • 减去最大的 3 个间距：$41 - 9 - 6 - 4 = 22$
   • 修正分段带来的端点计数：$22 + (4 - 1) = 25$
   • 最终结果：25

示例代码

/**
 * 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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号