1.每经过一个加油站，计算一次花费；
2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；
3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；
4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1D1、汽车油箱的容量CC（以升为单位）、每升汽油能行驶的距离D2D2、出发点每升汽油价格PP和沿途油站数NN（NN可以为零），油站ii离出发点的距离DiDi、每升汽油价格PiPi（i=1,2,…,Ni=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
第一行，D1D1，CC，D2D2，PP，NN。
接下来有NN行。
第i+1i+1行，两个数字，油站i离出发点的距离DiDi和每升汽油价格PiPi。
所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
26.95
#include<iostream> #include<algorithm> #include<vector> #include<iomanip> using namespace std; double d1, c1, d2, p, n,ans,d3,leave; int INF = 999999; struct node { double dis, cos; }; vector<node> a; bool comp(node aa, node bb) { return aa.dis <= bb.dis; } int f(int now) {//此函数学习于题解 int end = INF; for (int i = now + 1; i <= n && a[i].dis - a[now].dis <= d3; i++) { if (a[i].cos < a[now].cos) { ans += ((a[i].dis - a[now].dis - leave) / d2)*a[now].cos; leave = 0; return i; } if (end == INF ) end = i; if(a[i].cos < a[end].cos) end = i; } if (d1 - a[now].dis <= d3) { ans += ((d1 - a[now].dis - leave) / d2)*a[now].cos; return INF; } if (end == INF) { cout << "No Solution" << endl; return -1; } else { ans += c1 * a[now].cos; leave += (d3 - (a[end].dis - a[now].dis)); return end; } } int main() { cin >> d1 >> c1 >> d2 >> p >> n; node temp; temp.dis = 0; temp.cos = p; a.push_back(temp); for (int i = 1; i <= n; i++) { cin >> temp.dis >> temp.cos; a.push_back(temp); } d3 = d2 * c1; sort(a.begin(), a.end(), comp); int k= 0; while (k != INF) { k = f(k); if (k == -1) return 0; } cout << fixed << setprecision(2) << ans; return 0; }
原文：https://www.cnblogs.com/sxll/p/12678714.html