【NOIP】1999真题解析 luogu-P1016 旅行家的预算 | GESP四、五、六级以上推荐练习

发表于 2026/03/06

作者 OneCoder

次浏览 23 分钟阅读

NOIP 1999 普及组/提高组真题，是一道非常经典的贪心算法（Greedy Algorithm）思想考察题。题目的情景非常贴合生活，要求在油量有限的情况下以最小的费用到达目的地。通过这道题，可以很好地锻炼分解问题、寻找局部最优解并推导全局最优解的逻辑思维。适合GESP四（偏难）五、六级以上考生练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1016 [NOIP 1999 普及组/提高组] 旅行家的预算

题目要求

题目描述

一个旅行家想驾驶汽车以最小的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 $S$、汽车油箱的容量 $C$（以升为单位）、每升汽油能行驶的距离 $L$、出发点每升汽油价格 $P_0$ 和沿途油站数 $N$，油站 $i$ 离出发点的距离 $D_i$、油站 $i$ 每升汽油价格 $P_i\ (i=1,2,\dots,N)$，你需要求出最小的费用。

输入格式

第一行，四个实数 $S,C,L,P_0$ 和一个整数 $N$，含义见题目描述。接下来 $N$ 行，第 $i+1$ 行两个实数 $D_i$ 和 $P_i$，含义见题目描述。

输出格式

仅一行一个实数，代表最小的费用（四舍五入至小数点后两位）。如果无法到达目的地，输出 No Solution。

输入输出样例 #1

输入 #1

6 11.9 27.4 2.8 2
0 2.9
0 2.2

输出 #1

26.95

说明/提示

保证 $0 \leq N \leq 6$，$0 \leq S,C,L \leq 500$，且对于任意 $0\leq i \leq N$，均有 $0 \leq P_i \leq 500$，$0 \leq D_i \leq S$。

题目分析

这道题是经典的贪心算法问题。我们的目标是用最小的花费到达终点。贪心策略的核心是在每一步都做出当前看来最优的选择。

我们将起始点（距离为 0，油价为 $P_0$）也看作一个加油站，同时将终点（距离为 $S$）看作是一个“油价为 0”的虚拟加油站。这样所有的地方统一了起来。如果能直接到达这个“油价为 0”的终点，我们肯定会优先过去。

在任何一个加油站（假设当前在加油站 $A$），汽车加满油后能行驶的最大距离固定为 $C \times L$。我们只能观察距离 $A$ 不超过 $C \times L$ 的范围内所有可以到达的下一站，这里可以分出三种情况：

策略 1：找到比当前更便宜的加油站

如果在可达范围内有一个加油站 $B$，它的油价低于当前加油站 $A$ 的油价（$P_B < P_A$）。那么为了省钱，我们应该尽可能少地在 $A$ 加油，只要加到刚好能支撑开到 $B$ 的油量即可。到了 $B$ 之后，我们就能用更便宜的价格买油了。（注：如果有多个比 $A$ 便宜的加油站，我们应该选择其中最近的第一个以 $P_B < P_A$ 标准的站，因为只要到了便宜的站，后续路线就可以用更低的价格规划。）

策略 2：找不到比当前更便宜的加油站

如果在可达范围内所有的加油站油价都高于或等于当前站 $A$ 的油价，这就意味着 $A$ 是我们在满油续航范围内能遇到的最便宜的加油站。这就要求我们应该在 $A$ 站把油箱加满，充分利用当前的低价优势！加满后，我们去往下一个“相对最便宜”的地方——即在可达范围内寻找一个油价最低的加油站 $C$（此时 $P_C \geq P_A$），开过去后再作下一步打算。

策略 3：无法到达任何下一站

如果在满油状态下的最大可达范围内（即 $C \times L$），没有任何一个接下来的加油站（包括终点），说明中途会被迫抛锚，此时直接输出 No Solution。

有了这三条贪心准则，我们不断地把汽车从当前站推进到下一站，直到抵达终点（终点的油价是 0，只要在可达范围内，一定会触发第一种策略，刚好买满能到终点的油量）。

核心代码逻辑

本题可通过循环和递归两种方式实现。虽然两者的贪心策略完全一致，但在具体的代码实现逻辑推演上各有侧重。下面我们分别拆解这两种实现方式的核心逻辑步骤。

1. 循环迭代（while）实现的核心逻辑步骤

循环迭代法是自顶向下不断更新当前车辆“变量状态”的过程。其核心步骤如下：

第一步：寻找后续目标站点 每次循环开始时，在当前站 cur 满油可达的范围内（max_dist），向后遍历扫描站点：
- 如果发现比当前站更便宜的站，立刻锁定它为目标 next_station，并停止寻找（对应策略 1）。
- 如果范围内找不到更便宜的，则退而求其次，记录下范围内的相对最便宜的站 min_price_station（对应策略 2）。
- 如果范围内没有任何站，说明遇到了死胡同（对应策略 3）。
第二步：执行贪心策略并计算费用
- 触发策略 1： 若找到了 next_station。计算到达该站所需的油量。如果当前油箱剩的油不够，就只需在当前站买刚好能补齐差额的油（累加到总花费，意味着到达后剩余油量为 0）；如果本来剩余的油就够，则不花钱，直接开过去（剩余油量扣除消耗量）。
- 触发策略 2： 若只能去 min_price_station。这就要求必须在当前的站 把油箱加到底（加满） 以充分利用低价。把这笔“加满油”的钱累加到总花费计算中，而当汽车抵达目标站时，车内剩余油量就变成了满油量扣去这段路程的消耗。
- 触发策略 3： 没找到任何站，直接输出 No Solution 并终止程序。
第三步：推进状态进入下一轮 将当前所在的站点变量 cur 更新为第二步中找准的目标站点。只要当前不是终点，就不断回到第一步继续进行推进。

2. 递归（dfs）实现的核心逻辑步骤

递归法则是将每一站面临的情况作“切片”，然后把计算好的未来新状态压栈、交给下一层函数调用的过程。其核心步骤如下：

第一步：定义并检查递归状态 设计出递归签名 dfs(cur, remain_gas, current_cost)，以此携带当前所在站、剩余油量、已产生的总花费作为参数传递。每次进入函数时，必须首先检查递归终止边界：如果 cur 指向的已经是终点，直接输出并打印 current_cost 结算账单，结束递归。
第二步：横向寻找后续分支 这一步的查找逻辑与迭代完全一致。在当前的 cur 站向后扫描可达范围内的所有站点，寻找出符合上述贪心规则的更便宜的 next_station 或是相对最便宜的 min_price_station。这保证了每一次递归向下推演都只会有一个确定且唯一的最优分支（无后效性）。
第三步：纵向深入传递新状态 确定好目标后，不再是像循环那样修改全局或外层的值，而是前瞻性地计算好抵达下一站的全新状态，并向内传递：
- 若选择了 next_station分支： 判断是否需要补差价油。若需要，就把计算出的最新总费用和清零为 0 的剩余油量连同新站点编号传给下一层 dfs；如果底油足够开过去，则传下去不产生费用的旧花费和扣除消耗后的油量。
- 若选择了 min_price_station分支： 在这层计算出在当前站加满油所需的新总花费，以及抵达目标站后的剩余油量，将这两个新状态连同目标站编号传给下一层 dfs。
- 若遇到了死胡同： 同样直接输出抛锚死胡同的无解提示。

示例代码

解法一：贪心迭代（循环）实现

  
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

// 定义一个结构体表示沿途的站点
struct Station {
    double distance; // 距离起点的距离
    double price;    // 油价

    // 重载小于号，以便按距离对站点进行排序
    bool operator<(const Station& other) const {
        return distance < other.distance;
    }
};

int main() {
    double S, C, L, P0;
    int N;

    // 读入起点到终点距离、油箱容量、每升油行驶距离、起点油价和加油站数
    std::cin >> S >> C >> L >> P0 >> N;

    std::vector<Station> valid_stations;
    // 起点也是一个加油站（编号为 0）
    valid_stations.push_back({0.0, P0});

    for (int i = 0; i < N; ++i) {
        double d, p;
        std::cin >> d >> p;
        // 只保存位于起点和终点之间的有效加油站
        if (d < S) {
            valid_stations.push_back({d, p});
        }
    }
    // 终点可看作一个油价为 0 的站，这样能保证贪心时会优先开向终点
    valid_stations.push_back({S, 0.0});

    // 对所有的站点按距离起点的距离从小到大排序
    std::sort(valid_stations.begin(), valid_stations.end());

    double max_dist = C * L; // 满油状态下最多能行驶的距离
    double total_cost = 0.0; // 累计总花费
    double remain_gas = 0.0; // 当前油箱中剩余的油量

    int cur = 0; // 当前所在的站点索引
    int dest_idx = valid_stations.size() - 1; // 终点的索引

    while (cur < dest_idx) {
        int next_station = -1;
        int min_price_station = -1;
        double min_price = 1e9;

        // 在满油可达范围内寻找合适的下一站
        for (int i = cur + 1; i <= dest_idx && valid_stations[i].distance - valid_stations[cur].distance <= max_dist; ++i) {
            // 策略1：寻找第一个比当前站油价便宜的站点
            if (valid_stations[i].price < valid_stations[cur].price) {
                next_station = i;
                break; // 找到后直接打破循环，驶向第一家更便宜的站
            }
            // 策略2备用：如果没有更便宜的，记住可达范围内油价最便宜的站点
            if (valid_stations[i].price < min_price) {
                min_price = valid_stations[i].price;
                min_price_station = i;
            }
        }

        if (next_station != -1) {
            // 找到了更便宜的站点，只需买刚好能到那一站的油
            double gas_needed = (valid_stations[next_station].distance - valid_stations[cur].distance) / L;
            if (gas_needed > remain_gas) { // 如果剩下的油不够，才需要买油
                total_cost += (gas_needed - remain_gas) * valid_stations[cur].price;
                remain_gas = 0.0; // 到达下一站时油刚好用完（除了一开始剩下的部分刚好抵消）
            } else {
                remain_gas -= gas_needed; // 如果剩的油足够开过去，这里甚至不需要买油
            }
            cur = next_station;

        } else if (min_price_station != -1) {
            // 没有比当前更便宜的，说明当前油站是续航范围内最便宜的，果断加满！
            // 然后开过去可达范围内最便宜的那一站
            total_cost += (C - remain_gas) * valid_stations[cur].price;
            // 到达下一站后余下的油 = 新的满油状态 - 路上消耗的油
            remain_gas = C - (valid_stations[min_price_station].distance - valid_stations[cur].distance) / L;
            cur = min_price_station;

        } else {
            // 策略3：可达范围内没有任何站，直接抛锚死锁
            std::cout << "No Solution\n";
            return 0;
        }
    }

    // 输出保留两位小数的总体最低费用
    std::cout << std::fixed << std::setprecision(2) << total_cost << "\n";
    return 0;
}

解法二：递归（DFS）实现

  
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

struct Station {
    double distance; // 距离起点的距离
    double price;    // 油价

    // 重载小于号，以便按距离对站点进行排序
    bool operator<(const Station& other) const {
        return distance < other.distance;
    }
};

double S, C, L, P0; // 起点到终点距离、油箱容量、每升油行驶距离、起点油价
int N;              // 加油站数
std::vector<Station> valid_stations;
double max_dist;    // 满油状态下最多能行驶的距离

// 递归贪心求解
// 参数 cur: 当前在哪个站的索引
// 参数 remain_gas: 当前油箱中剩余的油量
// 参数 current_cost: 走到目前为止已经产生的累计花费
void dfs(int cur, double remain_gas, double current_cost) {
    // 递归终止条件：如果已经到达了最后一个站点（终点）
    if (cur == valid_stations.size() - 1) {
        // 打印最终的累计花费并结束递归，由于贪心选择的唯一性，这就是最优解
        std::cout << std::fixed << std::setprecision(2) << current_cost << "\n";
        return;
    }

    int next_station = -1;       // 记录策略1：第一个比当前便宜的油站编号
    int min_price_station = -1;  // 记录策略2：可达范围内的相对最便宜油站编号
    double min_price = 1e9;      // 用于维护相对最低价
    int dest_idx = valid_stations.size() - 1;

    // 在满油可达范围内寻找合适的下一站（查找逻辑与循环迭代完全一致）
    for (int i = cur + 1; i <= dest_idx && valid_stations[i].distance - valid_stations[cur].distance <= max_dist; ++i) {
        if (valid_stations[i].price < valid_stations[cur].price) {
            next_station = i; // 寻找第一个比当前站油价便宜的站点
            break;
        }
        if (valid_stations[i].price < min_price) {
            min_price = valid_stations[i].price; // 记录可达范围内油价最便宜的站点
            min_price_station = i;
        }
    }

    if (next_station != -1) {
        // 策略1：找到了更便宜的站点，只需买刚好能到那一站的油
        double gas_needed = (valid_stations[next_station].distance - valid_stations[cur].distance) / L;
        if (gas_needed > remain_gas) {
            // 如果剩余的油不够跑过去，需要补差价所需的油
            // 此时到达下一站后，油刚好耗尽为 0
            dfs(next_station, 0.0, current_cost + (gas_needed - remain_gas) * valid_stations[cur].price);
        } else {
            // 如果底油足够跑过去，不需要花钱买油，直接沿用以前的花费
            // 抵达下一站后，剩余的油等于现在的油扣减所需油量
            dfs(next_station, remain_gas - gas_needed, current_cost);
        }
    } else if (min_price_station != -1) {
        // 策略2：没有比当前更便宜的，说明当前油站是续航范围内最便宜的，果断加满！
        // 计算在当前这站加满所需的额外费用
        double cost_added = (C - remain_gas) * valid_stations[cur].price;
        // 计算抵达那一站后，扣去路上消耗，油箱里还会剩下多少油
        double gas_left = C - (valid_stations[min_price_station].distance - valid_stations[cur].distance) / L;
        // 让这两个新状态伴随递归深入
        dfs(min_price_station, gas_left, current_cost + cost_added);
    } else {
        // 策略3：可达范围内没有任何站，直接抛锚死锁
        std::cout << "No Solution\n";
    }
}

int main() {
    // 读入数据
    std::cin >> S >> C >> L >> P0 >> N;

    // 起点也是一个加油站（编号为 0）
    valid_stations.push_back({0.0, P0});
    for (int i = 0; i < N; ++i) {
        double d, p;
        std::cin >> d >> p;
        // 过滤掉终点之外的无效站
        if (d < S) {
            valid_stations.push_back({d, p});
        }
    }
    // 把终点标记为一个价格为 0 的站
    valid_stations.push_back({S, 0.0});

    // 所有合法站进行排序
    std::sort(valid_stations.begin(), valid_stations.end());
    max_dist = C * L; // 计算满油最大续航

    // 开启递归推演：
    // 从起点 0 出发，初始剩余油量为 0，初始花费为 0
    dfs(0, 0.0, 0.0);

    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)，考试认证学员交流，互帮互助

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

NOIP, 1999

NOIP C++ 贪心模拟

本文由作者按照 CC BY-NC-SA 4.0 进行授权