1999年NOIP普及组旅行家的预算（洛谷P1016）：贪心算法实战...
https://dajuwangluo.cn/zb_users/upload/2025/07/202507111752246219626539.jpg一、问题背景旅行家的预算是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, P}; // 起点加油站
for (int i = 1; i <= N; ++i) {
cin >> stations.distance >> stations.price;
}
stations = {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.distance > max_distance) {
cout << "No Solution" << endl;
return 0;
}
while (current_station <= N) {
// 寻找下一个比当前便宜的加油站
int next_station = current_station + 1;
double min_price = stations.price;
int cheapest_station = -1;
// 在可达范围内寻找最便宜的加油站
while (next_station <= N+1 &&
stations.distance - stations.distance <= max_distance) {
if (stations.price < min_price) {
min_price = stations.price;
cheapest_station = next_station;
break; // 找到第一个更便宜的加油站就停止
}
next_station++;
}
if (cheapest_station != -1) {
// 计算需要加的油量
double distance = stations.distance - stations.distance;
double needed_gas = distance / D2 - current_gas;
if (needed_gas > 0) {
total_cost += needed_gas * stations.price;
current_gas = 0;
} else {
current_gas -= distance / D2;
}
current_station = cheapest_station;
} else {
// 没有更便宜的加油站，加满油到最远的加油站
if (stations.distance + max_distance >= D1) {
// 可以直接到达终点
double distance = D1 - stations.distance;
double needed_gas = distance / D2 - current_gas;
if (needed_gas > 0) {
total_cost += needed_gas * stations.price;
}
cout << fixed << setprecision(2) << total_cost << endl;
return 0;
}
// 检查是否能到达下一个加油站
next_station = current_station + 1;
if (next_station > N ||
stations.distance - stations.distance > max_distance) {
cout << "No Solution" << endl;
return 0;
}
// 加满油到下一个加油站
total_cost += (C - current_gas) * stations.price;
current_gas = C - (stations.distance - stations.distance) / D2;
current_station = next_station;
}
}
cout << fixed << setprecision(2) << total_cost << endl;
return 0;
}
五、常见错误与优化
[*]可达性检查：必须首先检查能否到达第一个加油站
[*]浮点数精度：使用double类型并控制输出精度
[*]边界条件：特别注意终点处理和无解情况
转自：1999年NOIP普及组旅行家的预算（洛谷P1016）：贪心算法实战指南
页:
[1]