解法一:贪心
将终点视为一个价格为0的加油站,对所有加油站按照距离排序。
考虑起点处无加油站的情况。
加油的贪心策略如下。
- 和当前位置相比,如果最大可及范围有价格更加便宜的加油站,则选择最近的前往,在当前位置加油至足够到达即可
- 如果没有更便宜的加油站,在当前位置加满油,然后行驶到相对最便宜的加油站
- 如果没有加油站了,说明无法到达终点,加满油计算最大行驶距离。
```cpp
include
using namespace std; const double EPS = 1e-6;
class Station { public: double price; double dis;
Station() {}
Station(double price, int dis) : price(price), dis(dis) {}
};
bool cmp(Station o1, Station o2) { return o1.dis < o2.dis; }
Station stations[505];
int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(2);
double C_max, D, D_avg;
int N;
cin >> C_max >> D >> D_avg >> N;
for (int i = 0; i < N; ++i) {
cin >> stations[i].price >> stations[i].dis;
}
sort(stations, stations + N, cmp);
// 终点视为价格为0的加油站
stations[N].price = 0.0;
stations[N].dis = D;
N++;
// 出发点没有加油站
if (stations[0].dis != 0) {
cout << "The maximum travel distance = 0.00\n";
return 0;
}
double gas = 0.0;
double cost = 0.0;
double cur = 0.0;
double end;
int curIndex = 0;
while (cur < D) {
// 找范围内最便宜的加油站
end = cur + C_max * D_avg;
// 是否有下一个加油站可达
bool flag = false;
int cheapStation = curIndex + 1;
for (int i = curIndex + 1; i < N && stations[i].dis <= end; ++i) {
flag = true;
if (stations[i].price <= stations[cheapStation].price) {
cheapStation = i;
if (stations[cheapStation].price < stations[curIndex].price) {
break;
}
}
}
if (!flag) {
cout << "The maximum travel distance = " << end << '\n';
return 0;
}
if (stations[cheapStation].price > stations[curIndex].price) {
// 当前加油站最便宜, 直接加满
// 然后跑到可及范围内最便宜的加油站
cost += (C_max - gas) * stations[curIndex].price;
gas = C_max - (stations[cheapStation].dis - cur) / D_avg;
cur = stations[cheapStation].dis;
curIndex = cheapStation;
} else {
// 可及范围有更便宜的加油站
// 加油确保能跑到即可
double need = (stations[cheapStation].dis - cur) / D_avg;
if (gas < need) {
cost += (need - gas) * stations[curIndex].price;
gas = 0.0;
} else {
gas -= need;
}
cur = stations[cheapStation].dis;
curIndex = cheapStation;
}
}
cout << cost << '\n';
} ```