题解：P1016 [NOIP 1999 普及组/提高组] 旅行家的预算

chenlc · 2026-05-13 22:06:44 · 题解

思路

题目求的是最小的费用，也就是说要让买每一升油的价格尽量的低，于是考虑贪心。

在预处理部分，我们把所有加油站的离起点的距离与每升汽油价格加入序列。将起点当作一个距离为 0，价格为 P_0 的加油站；将终点当作一个距离为 S，价格为 0 的加油站。把起点和终点也加入序列，按照距离进行排序。

设 maxd 为最大行驶距离（也就是 C \times L）。如果两个加油站之间的距离大于 maxd，那么输出 No Solution。

假设当前在加油站 i：

• 如果在 maxd 范围内，加油站 j 更便宜（P_j < P_i）。我们肯定去加油站 j 加油。于是，只需加够刚好能到达第一个比当前站便宜的 j 站的油即可；
• 如果在 maxd 范围内，没有加油站更便宜。因为当前 i 是这一段路程中最便宜的，为了省钱，我们直接加满油，然后继续往后走。

注意：为了防止毒瘤数据，当 D_i 小于 S 的时候才加入。

upd on 2026/05/14：细化了表达。

代码

#include <bits/stdc++.h>
using namespace std;
double S, C, L, P0;
double maxd, oil, ans;
int n;
struct node{
    double dist, price;
};
bool cmp(node x, node y){
    return x.dist < y.dist;
}
int main(){
    vector<node> sta;
    scanf("%lf%lf%lf%lf%d", &S, &C, &L, &P0, &n);
    sta.push_back({0, P0});
    sta.push_back({S, 0});
    for(int i = 1; i <= n; i++){
        double d, p;
        scanf("%lf%lf", &d, &p);
        if(d >= S){
            continue;
        }
        sta.push_back({d, p});
    }
    sort(sta.begin(), sta.end(), cmp);
    maxd = C * L;
    for(int i = 0; i < sta.size() - 1;){
        if(sta[i + 1].dist - sta[i].dist > maxd){
            printf("No Solution\n");
            return 0;
        }
        int cheaper = -1;
        for(int j = i + 1; j < sta.size(); j++){
            if(sta[j].dist - sta[i].dist > maxd){
                break;
            }
            if(sta[j].price < sta[i].price){
                cheaper = j;
                break;
            }
        }
        if(cheaper != -1){
            double need = (sta[cheaper].dist - sta[i].dist) / L;
            if(oil < need){
                ans += (need - oil) * sta[i].price;
                oil = 0;
            }
            else{
                oil -= need;
            }
            i = cheaper;
        }
        else{
            double full = C - oil;
            oil = C - (sta[i + 1].dist - sta[i].dist) / L;
            ans += full * sta[i].price;
            i++;
        }
    }
    printf("%.2lf\n", ans);
}