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

15303105423

一、问题背景

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

二、数据结构设计struct Station {    double distance;  // 加油站距离起点的位置    double price;     // 该加油站的油价};

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

三、核心算法思路

• 加油站预处理：将起点和终点也视为特殊加油站，并按距离排序
• 可达性检查：计算满油能行驶的最大距离（C*D2）
• 贪心策略：
  
  
  • 优先寻找当前可达范围内比当前站更便宜的加油站
  • 若无更便宜加油站，则在当前站加满油
  • 每次只加到达下一站所需的油量
    
    

四、完整代码解析

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <iomanip>
   
5. using namespace std;
   
6. 
   
7. struct Station {
   
8.     double distance;
   
9.     double price;
   
10. };
    
11. 
    
12. int main() {
    
13.     double D1, C, D2, P;
    
14.     int N;
    
15.     cin >> D1 >> C >> D2 >> P >> N;
    
16.    
    
17.     vector<Station> stations(N+2);
    
18.     stations[0] = {0, P}; // 起点加油站
    
19.     for (int i = 1; i <= N; ++i) {
    
20.         cin >> stations[i].distance >> stations[i].price;
    
21.     }
    
22.     stations[N+1] = {D1, 0}; // 终点设为虚拟加油站
    
23.    
    
24.     // 按距离排序加油站
    
25.     sort(stations.begin(), stations.end(), [](const Station& a, const Station& b) {
    
26.         return a.distance < b.distance;
    
27.     });
    
28.    
    
29.     double max_distance = C * D2; // 满油能行驶的最大距离
    
30.     double current_gas = 0; // 当前油量
    
31.     double total_cost = 0; // 总花费
    
32.     int current_station = 0; // 当前所在加油站
    
33.    
    
34.     // 检查是否能到达第一个加油站
    
35.     if (stations[1].distance > max_distance) {
    
36.         cout << "No Solution" << endl;
    
37.         return 0;
    
38.     }
    
39.    
    
40.     while (current_station <= N) {
    
41.         // 寻找下一个比当前便宜的加油站
    
42.         int next_station = current_station + 1;
    
43.         double min_price = stations[current_station].price;
    
44.         int cheapest_station = -1;
    
45.         
    
46.         // 在可达范围内寻找最便宜的加油站
    
47.         while (next_station <= N+1 &&
    
48.                stations[next_station].distance - stations[current_station].distance <= max_distance) {
    
49.             if (stations[next_station].price < min_price) {
    
50.                 min_price = stations[next_station].price;
    
51.                 cheapest_station = next_station;
    
52.                 break; // 找到第一个更便宜的加油站就停止
    
53.             }
    
54.             next_station++;
    
55.         }
    
56.         
    
57.         if (cheapest_station != -1) {
    
58.             // 计算需要加的油量
    
59.             double distance = stations[cheapest_station].distance - stations[current_station].distance;
    
60.             double needed_gas = distance / D2 - current_gas;
    
61.             if (needed_gas > 0) {
    
62.                 total_cost += needed_gas * stations[current_station].price;
    
63.                 current_gas = 0;
    
64.             } else {
    
65.                 current_gas -= distance / D2;
    
66.             }
    
67.             current_station = cheapest_station;
    
68.         } else {
    
69.             // 没有更便宜的加油站，加满油到最远的加油站
    
70.             if (stations[current_station].distance + max_distance >= D1) {
    
71.                 // 可以直接到达终点
    
72.                 double distance = D1 - stations[current_station].distance;
    
73.                 double needed_gas = distance / D2 - current_gas;
    
74.                 if (needed_gas > 0) {
    
75.                     total_cost += needed_gas * stations[current_station].price;
    
76.                 }
    
77.                 cout << fixed << setprecision(2) << total_cost << endl;
    
78.                 return 0;
    
79.             }
    
80.             
    
81.             // 检查是否能到达下一个加油站
    
82.             next_station = current_station + 1;
    
83.             if (next_station > N ||
    
84.                 stations[next_station].distance - stations[current_station].distance > max_distance) {
    
85.                 cout << "No Solution" << endl;
    
86.                 return 0;
    
87.             }
    
88.             
    
89.             // 加满油到下一个加油站
    
90.             total_cost += (C - current_gas) * stations[current_station].price;
    
91.             current_gas = C - (stations[next_station].distance - stations[current_station].distance) / D2;
    
92.             current_station = next_station;
    
93.         }
    
94.     }
    
95.    
    
96.     cout << fixed << setprecision(2) << total_cost << endl;
    
97.     return 0;
    
98. }

复制代码

五、常见错误与优化

• 可达性检查：必须首先检查能否到达第一个加油站
• 浮点数精度：使用double类型并控制输出精度
• 边界条件：特别注意终点处理和无解情况
  
  

来源：竞赛学习