1999年NOIP普及组旅行家的预算（洛谷P1016）：贪心算法实战指南

2天前比赛题解55

一、问题背景

旅行家的预算是NOIP1999普及组的经典题目，考察贪心算法在实际问题中的应用。题目描述一位旅行家需要从起点到终点，途中有若干个加油站，每个加油站油价不同，要求在有限油箱容量下规划最优加油策略，使总花费最少。

二、数据结构设计

struct Station {
    double distance;  // 加油站距离起点的位置
    double price;     // 该加油站的油价
};

使用结构体存储每个加油站的信息，便于后续处理。

三、核心算法思路

加油站预处理：将起点和终点也视为特殊加油站，并按距离排序
可达性检查：计算满油能行驶的最大距离（C*D2）
贪心策略：

优先寻找当前可达范围内比当前站更便宜的加油站
若无更便宜加油站，则在当前站加满油
每次只加到达下一站所需的油量

四、完整代码解析

#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 = 0;
            } else {
                current_gas -= distance / D2;
            }
            current_station = cheapest_station;
        } else {
            // 没有更便宜的加油站，加满油到最远的加油站
            if (stations[current_station].distance + max_distance >= D1) {
                // 可以直接到达终点
                double distance = D1 - stations[current_station].distance;
                double needed_gas = distance / D2 - current_gas;
                if (needed_gas > 0) {
                    total_cost += needed_gas * stations[current_station].price;
                }
                cout << fixed << setprecision(2) << total_cost << endl;
                return 0;
            }
            
            // 检查是否能到达下一个加油站
            next_station = current_station + 1;
            if (next_station > N || 
                stations[next_station].distance - stations[current_station].distance > max_distance) {
                cout << "No Solution" << endl;
                return 0;
            }
            
            // 加满油到下一个加油站
            total_cost += (C - current_gas) * stations[current_station].price;
            current_gas = C - (stations[next_station].distance - stations[current_station].distance) / D2;
            current_station = next_station;
        }
    }
    
    cout << fixed << setprecision(2) << total_cost << endl;
    return 0;
}