洛谷P1016——旅行家的预算

这是一道贪心算法的题，算法核心是根据距离和油量价格的更新策略，以最小的开销到达目的地。

算法思路：

代码：

#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <limits> using namespace std; struct Station { double distance; // 到起点的距离 double price; // 油价 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); double S, C, L, P0; int N; cin >> S >> C >> L >> P0 >> N; vector<Station> stations(N + 2); stations[0] = { 0.0, P0 }; // 起点 for (int i = 1; i <= N; i++) { cin >> stations[i].distance >> stations[i].price; } stations[N + 1] = { S, 0.0 }; // 终点虚拟站，油价不计 // 按距离排序 sort(stations.begin(), stations.end(), [](const Station& a, const Station& b) { return a.distance < b.distance; }); double maxDistancePerFullTank = C * L; // 检查是否存在不可达情况 for (int i = 1; i <= N + 1; i++) { if (stations[i].distance - stations[i - 1].distance > maxDistancePerFullTank) { cout << "No Solution\n"; return 0; } } double totalCost = 0.0; // 总费用 double currentFuel = 0.0; // 当前油量（升） int cur = 0; // 当前所在站点索引 while (cur < N + 1) { // 到终点前循环 double maxReach = stations[cur].distance + maxDistancePerFullTank; int nextStation = -1; double minPriceInRange = numeric_limits<double>::max(); // 遍历可达范围内的加油站 for (int i = cur + 1; i <= N + 1; i++) { if (stations[i].distance > maxReach) break; if (stations[i].price < stations[cur].price) { // 找到比当前站油价低的第一个站 nextStation = i; break; } // 否则记录可达范围内最便宜的站 if (stations[i].price < minPriceInRange) { minPriceInRange = stations[i].price; nextStation = i; } } double neededFuel = (stations[nextStation].distance - stations[cur].distance) / L; if (stations[nextStation].price < stations[cur].price) { // 下一站比当前便宜，只加够油 if (currentFuel < neededFuel) { totalCost += (neededFuel - currentFuel) * stations[cur].price; currentFuel = neededFuel; } } else { // 当前站是可达范围内最便宜的，加满油 if (currentFuel < C) { totalCost += (C - currentFuel) * stations[cur].price; currentFuel = C; } } // 驶向下一站 currentFuel -= neededFuel; cur = nextStation; } cout << fixed << setprecision(2) << totalCost << "\n"; return 0; }

说明：
（1）ios::sync_with_stdio(false)：用于断开C++标准流（cin/cout）与C标准流（scanf/printf）的同步，取消默认的缓冲区共享，从而大幅提升读写速度

（2）cin.tie(nullptr)：解除cin与cout的绑定，避免不必要的刷新开销

在处理大型文本文件、大规模数据、限时竞赛中可以使用此方法提升效率（本题数据规模小可不用）