1 条题解
-
0
【本题解由站长编写】
经典贪心:在当前油站,先看可达范围内有没有更便宜的油站——有就只买刚好够到最近一个便宜站的油;没有时若终点可达就只买刚好够到终点的油;否则加满油,开到可达范围内最便宜的油站。任何一段路都存在可达的油站,否则输出 No Solution。注意先找便宜站再考虑直达:终点可达但范围内有更便宜的油站时,绕到便宜站买更划算。费用四舍五入保留两位小数。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { double D1, C, D2, P; long long N; cin >> D1 >> C >> D2 >> P >> N; vector<double> pos(1, 0.0), price(1, P); for (long long i = 0; i < N; i++) { double d, p; cin >> d >> p; pos.push_back(d); price.push_back(p); } vector<int> order(pos.size()); for (int i = 0; i < (int)order.size(); i++) order[i] = i; sort(order.begin() + 1, order.end(), [&](int a, int b) { return pos[a] < pos[b]; }); const double EPS = 1e-9; double range = C * D2, fuel = 0, cost = 0; int cur = 0; while (true) { // Only stations strictly ahead of the current one can be visited next. int cheaper = -1, target = -1; for (int t = 1; t < (int)order.size(); t++) { int s = order[t]; if (pos[s] <= pos[cur]) continue; if (pos[s] - pos[cur] > range + EPS) break; if (price[s] < price[cur] && cheaper == -1) cheaper = s; if (target == -1 || price[s] < price[target]) target = s; } if (cheaper != -1) { double need = (pos[cheaper] - pos[cur]) / D2; if (need > fuel) { cost += (need - fuel) * price[cur]; fuel = 0; } else fuel -= need; cur = cheaper; continue; } if (D1 - pos[cur] <= range + EPS) { double need = (D1 - pos[cur]) / D2; if (need > fuel) cost += (need - fuel) * price[cur]; printf("%.2f\n", cost); return 0; } if (target == -1) { puts("No Solution"); return 0; } cost += (C - fuel) * price[cur]; fuel = C - (pos[target] - pos[cur]) / D2; cur = target; } }
- 1
信息
- ID
- 4287
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者