gpt-4o-2024-05-13· OpenAI
WildChat-4.8M (AI2)
Untitled conversation
- User
[NOIP1999 提高组] 旅行家的预算
题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 、汽车油箱的容量 (以升为单位)、每升汽油能行驶的距离 、出发点每升汽油价格和沿途油站数 ( 可以为零),油站 离出发点的距离 、每升汽油价格 ()。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出
No Solution。输入格式
第一行,,,,,。
接下来有 行。
第 行,两个数字,油站 离出发点的距离 和每升汽油价格 。
输出格式
所需最小费用,计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出
No Solution。样例 #1
样例输入 #1
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2样例输出 #1
26.95提示
,其余数字 。
使用c++解决此题目
- Assistant
下面是使用C++编写的解决方案:
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; struct Station { double distance; double price; }; bool compareStations(Station a, Station b) { return a.distance < b.distance; } int main() { double D1, C, D2, P; int N; cin >> D1 >> C >> D2 >> P >> N; vector<Station> stations(N + 1); stations[0] = {0, P}; // Add the start point as a "station" for (int i = 1; i <= N; ++i) { cin >> stations[i].distance >> stations[i].price; } sort(stations.begin(), stations.end(), compareStations); if (stations[1].distance > C * D2) { cout << "No Solution" << endl; return 0; } double currentTank = 0; double totalCost = 0; int i = 0; while (i <= N) { int nextStationIndex = -1; for (int j = i + 1; j <= N; ++j) { if (stations[j].distance - stations[i].distance <= C * D2) { if (nextStationIndex == -1 || stations[j].price < stations[nextStationIndex].price) { nextStationIndex = j; if (stations[j].price < stations[i].price) { break; } } } else { break; } } if (nextStationIndex == -1) { if (D1 - stations[i].distance <= C * D2) { double fuelNeeded = (D1 - stations[i].distance) / D2 - currentTank; if (fuelNeeded > 0) { totalCost += fuelNeeded * stations[i].price; } cout << fixed << setprecision(2) << totalCost << endl; return 0; } else { cout << "No Solution" << endl; return 0; } } double distanceToNext = stations[nextStationIndex].distance - stations[i].distance; double fuelNeeded = distanceToNext / D2; if (stations[nextStationIndex].price < stations[i].price) { if (fuelNeeded > currentTank) { totalCost += (fuelNeeded - currentTank) * stations[i].price; currentTank = fuelNeeded; } } else { if (C > currentTank) { totalCost += (C - currentTank) * stations[i].price; currentTank = C; } } currentTank -= fuelNeeded; i = nextStationIndex; } return 0; }解释
- 结构体
Station:用来存储每个加油站的距离和每升汽油价格。 - 比较函数
compareStations:用于按距离对加油站进行排序。 - 输入数据:首先读取起点到终点的距离、油箱容量、每升汽油可行驶的距离、出发点油价及加油站数量,然后读取各个加油站的数据并存入
stations向量。 - 起点处理:将起点作为第一个加油站。
- 排序:按距离对所有加油站(包括起点)进行排序。
- 检查第一站:如果第一个加油站距离超过油箱满油能开到的距离,则直接输出
No Solution。 - 遍历加油站:以贪心策略计算到达每个加油站时应加多少油,通过比较选择最优的下一个加油站。
- 目标检测:如果目标能在当前油量下到达,并且不需再加油,直接输出总费用,否则判定为
No Solution。
希望这个解析对你理解代码有所帮助。如果有其他问题,请随时提出。
- 结构体