按距离排序后做站点贪心：若前方有更便宜站就只买到够到它，否则当前站加满并去可达范围内最低价站。
OJ: luogu
题目 ID: P1016
难度:普及+/提高
标签:贪心模拟noip
日期: 2026-06-20 13:02
题意
从起点开车到终点，初始油箱为空。
已知：
- 总路程
S - 油箱容量
C - 每升油可行驶距离
L - 起点油价
P0 - 沿途若干加油站的位置和油价
要求用最小花费到达终点；如果到不了，输出 No Solution。
思路
先看一个可以直接验证想法的朴素解：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
const long double EPS = 1e-10L;
const long double INF = 1e100L;
struct Station {
long double dist;
long double price;
};
struct StateKey {
int idx;
long long fuel_key;
bool operator < (const StateKey &other) const {
if (idx != other.idx) return idx < other.idx;
return fuel_key < other.fuel_key;
}
};
long double total_dist, tank_cap, dist_per_liter, start_price;
int station_cnt;
Station st[MAXN];
map<StateKey, long double> memo;
bool cmp_station(const Station &a, const Station &b) {
return a.dist < b.dist;
}
long long encode_fuel(long double fuel) {
if (fuel < 0 && fuel > -EPS) fuel = 0;
return llround(fuel * 100000000.0L);
}
long double decode_fuel(long long key) {
return (long double)key / 100000000.0L;
}
long double dfs(int idx, long long fuel_key) {
if (idx == station_cnt) return 0;
StateKey state = {idx, fuel_key};
if (memo.count(state)) return memo[state];
long double fuel = decode_fuel(fuel_key);
long double best = INF;
// 暴力枚举离开当前站时，油箱里可能保留的油量。
// 有意义的选择包括：
// 1. 不再买油，直接用当前油量；
// 2. 加满；
// 3. 加到刚好能到某个后续站点。
vector<long double> candidates;
candidates.push_back(fuel);
candidates.push_back(tank_cap);
for (int i = idx + 1; i <= station_cnt; i++) {
long double need = (st[i].dist - st[idx].dist) / dist_per_liter;
if (need - tank_cap <= EPS) {
candidates.push_back(need);
}
}
sort(candidates.begin(), candidates.end());
candidates.erase(unique(candidates.begin(), candidates.end(), [](long double a, long double b) {
return fabsl(a - b) <= EPS;
}), candidates.end());
for (long double leave_fuel : candidates) {
if (leave_fuel + EPS < fuel) continue;
if (leave_fuel - tank_cap > EPS) continue;
long double buy_cost = (leave_fuel - fuel) * st[idx].price;
for (int j = idx + 1; j <= station_cnt; j++) {
long double need = (st[j].dist - st[idx].dist) / dist_per_liter;
if (need - leave_fuel > EPS) continue;
long double remain = leave_fuel - need;
long double next_cost = dfs(j, encode_fuel(remain));
if (next_cost >= INF / 2) continue;
best = min(best, buy_cost + next_cost);
}
}
memo[state] = best;
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> total_dist >> tank_cap >> dist_per_liter >> start_price >> station_cnt;
st[0].dist = 0;
st[0].price = start_price;
for (int i = 1; i <= station_cnt; i++) {
cin >> st[i].dist >> st[i].price;
}
st[station_cnt + 1].dist = total_dist;
st[station_cnt + 1].price = 0;
station_cnt++;
sort(st, st + station_cnt + 1, cmp_station);
long double ans = dfs(0, encode_fuel(0));
if (ans >= INF / 2) {
cout << "No Solution\n";
} else {
cout << fixed << setprecision(2) << (double)(ans + 1e-9L) << '\n';
}
return 0;
}这题的关键不在搜索，而在一个很典型的加油贪心。
把起点也看作一个站，再把终点看作价格为 0 的虚拟站。
站点按距离排序后，站在当前站时，只关心“满油能到达的范围”。
接下来分两种情况。
1. 前方存在更便宜的站
如果在可达范围内能找到一个比当前站更便宜的站， 那么当前站只需要买“刚好够到那个更便宜站”的油。
因为多买出来的那部分油，本来可以留到更便宜的站再买， 提前在当前更贵的地方买只会让总费用更高。
2. 前方不存在更便宜的站
如果当前满油可达范围内所有站都不比当前便宜， 那说明在这一整段路里，当前站就是最划算的买油点。
所以这时最优策略是：
- 直接把油箱加满；
- 然后开到可达范围内油价最低的那个站。
无解情况
如果从当前站出发，满油后仍然连一个后继站都到不了，
那就说明根本无法到达终点，直接输出 No Solution。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
const long double EPS = 1e-12L;
struct Station {
long double dist; // 这个加油点距离起点的距离
long double price; // 这个加油点的油价
};
long double total_dist, tank_cap, dist_per_liter, start_price;
int station_cnt;
Station st[MAXN];
bool cmp_station(const Station &a, const Station &b) {
return a.dist < b.dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> total_dist >> tank_cap >> dist_per_liter >> start_price >> station_cnt;
st[0].dist = 0;
st[0].price = start_price;
for (int i = 1; i <= station_cnt; i++) {
cin >> st[i].dist >> st[i].price;
}
// 把终点看成一个“价格为 0 的特殊站点”，这样逻辑会统一很多。
st[station_cnt + 1].dist = total_dist;
st[station_cnt + 1].price = 0;
station_cnt++;
sort(st, st + station_cnt + 1, cmp_station);
long double max_reach = tank_cap * dist_per_liter; // 满油最多能跑多远
long double fuel = 0; // 当前油箱里的油量（升）
long double answer = 0; // 总花费
// 找到排序后真正的起点位置。
int cur = -1;
for (int i = 0; i <= station_cnt; i++) {
if (fabsl(st[i].dist) <= EPS && fabsl(st[i].price - start_price) <= EPS) {
cur = i;
break;
}
}
while (cur < station_cnt) {
int first_cheaper = -1;
int best_station = -1;
// 在满油可达范围内：
// 1. 找第一个比当前更便宜的站；
// 2. 如果找不到，记下范围内油价最低的站。
for (int i = cur + 1; i <= station_cnt; i++) {
long double delta = st[i].dist - st[cur].dist;
if (delta - max_reach > EPS) break;
if (st[i].price + EPS < st[cur].price) {
first_cheaper = i;
break;
}
if (best_station == -1 || st[i].price + EPS < st[best_station].price) {
best_station = i;
}
}
// 连一个可达站都没有，说明无解。
if (first_cheaper == -1 && best_station == -1) {
cout << "No Solution\n";
return 0;
}
if (first_cheaper != -1) {
// 前面有更便宜的站，只买“恰好够到它”的油。
long double need = (st[first_cheaper].dist - st[cur].dist) / dist_per_liter;
if (fuel + EPS < need) {
answer += (need - fuel) * st[cur].price;
fuel = need;
}
fuel -= need;
cur = first_cheaper;
} else {
// 前面没有更便宜的站，当前站就是这段范围里最便宜的，
// 所以把油箱加满，然后开到范围内油价最低的那个站。
if (fuel + EPS < tank_cap) {
answer += (tank_cap - fuel) * st[cur].price;
fuel = tank_cap;
}
long double need = (st[best_station].dist - st[cur].dist) / dist_per_liter;
fuel -= need;
cur = best_station;
}
}
cout << fixed << setprecision(2) << (double)(answer + 1e-9L) << '\n';
return 0;
}复杂度
设总站点数为 N + 2（包含起点和终点虚拟站）。
每一步向右扫描当前可达范围，所以时间复杂度是
总结
这道题最重要的是把“买多少油”转化成价格比较问题：
- 有更便宜站，就只买够到它；
- 没有更便宜站，就当前加满。
一旦这个贪心规则想清楚，代码实现就很直接了。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
