当前位置：首页 > 入门组 > 【1999NOIP普及组】（洛谷P1016）旅行家的预算解题报告（附代码+注释）

【1999NOIP普及组】（洛谷P1016）旅行家的预算解题报告（附代码+注释）

2个月前 (07-04)

一、题目解读

题目要求解决旅行家从起点到终点（D1公里）的预算问题，需在沿途N个加油站中规划加油策略，使总费用最小化。每个加油站有不同油价和距离，汽车每升油可行驶D2公里，初始油量为C升，终点无加油站。需在满足油量限制的条件下，找到最经济的加油方案。

二、解题思路

核心思路为动态规划结合贪心算法。通过以下关键点实现：

1. 虚拟终点：将终点视为价格为零的虚拟加油站，确保算法完整性。

2. 距离排序：按距离对加油站排序，便于按顺序遍历。

3. 贪心选择：每次优先选择当前可达范围内最便宜的加油站，避免回溯。

4. 油量管理：实时计算当前油量能否到达下一站，按需加油至恰好可到达最远点。

三、解题步骤

1. 数据输入：读取起点距离D1、初始油量C、终点距离D2、初始油价P及N个加油站信息。

2. 构造虚拟终点：添加距离为D1、油价为0的虚拟终点站。

3. 排序加油站：按距离升序排序，确保遍历顺序正确。

4. 初始化变量：记录当前油量、总费用、当前位置。

5. 核心循环：

寻找当前可达范围内最便宜的加油站（贪心）。

计算到达该站所需油量，若当前油量不足则补充。

更新总费用与位置，直至到达终点。

6. 边界判断：若无法到达第一个加油站，直接输出无解。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Station {  // 定义加油站结构体  
    double distance;  // 距离起点距离  
    double price;  // 油价  
};

int main() {
    double D1, C, D2, P;  // 输入参数  
    int N;  
    cin >> D1 >> C >> D2 >> P >> N;
    
    vector<Station> stations(N+2);  // 包含虚拟起点和终点  
    stations[0] = {0, P};  // 起点加油站  
    for (int i = 1; i <= N; ++i) {  
        cin >> stations[i].distance >> stations[i].price;  
    }  
    stations[N+1] = {D1, 0};  // 虚拟终点站  

    // 按距离排序  
    sort(stations.begin(), stations.end(), [](const Station& a, const Station& b) {  
        return a.distance < b.distance;  
    });

    double max_distance = C * D2;  // 满油可行驶距离  
    double current_gas = 0;  // 当前油量  
    double total_cost = 0;  // 总费用  
    int current_station = 0;  // 当前位置  

    // 检查能否到达第一个加油站  
    if (stations[1].distance > max_distance) {  
        cout << "No Solution" << endl;  
        return 0;  
    }

    while (current_station <= N) {  
        int next_station = current_station + 1;  
        double min_price = stations[current_station].price;  
        int cheapest_station = -1;  

        // 寻找可达范围内最便宜的加油站  
        while (next_station <= N+1 &&  
               stations[next_station].distance - stations[current_station].distance <= max_distance) {  
            if (stations[next_station].price < min_price) {  
                min_price = stations[next_station].price;  
                cheapest_station = next_station;  
                break;  // 找到第一个更便宜的站即退出  
            }  
            next_station++;  
        }  

        if (cheapest_station!= -1) {  
            // 计算到达下一站所需油量  
            double distance = stations[cheapest_station].distance - stations[current_station].distance;  
            double needed_gas = distance / D2 - current_gas;  
            if (needed_gas > 0) {  // 若需要加油  
                total_cost += needed_gas * stations[current_station].price;  // 按当前站油价计费  
                current_gas = max_distance;  // 补满油  
            } else {  
                current_gas -= needed_gas;  // 否则消耗油量  
            }  
            current_station = cheapest_station;  // 更新位置  
        } else {  // 若找不到更便宜的站，直接前往终点  
            total_cost += (D1 - stations[current_station].distance) / D2 * stations[current_station].price;  
            break;  
        }  
    }  

    cout << fixed << setprecision(2) << total_cost << endl;  // 输出结果  
    return 0;  
}