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

· · 题解

0. 题外话

为了见证历史赶时间写的题解，后面会完善的，希望管理员大人给过。

球球了。

1. 题意概括

你需要驾驶汽车以最小的费用从起点到终点，出发时油箱是空的。沿途有 N 个油站，每个油站都会售卖汽油（废话）。给定起点与终点的距离 S、汽车油箱的容量 C、每单位汽油能行驶的距离 L 和起点每单位汽油价格 P_0，以及每个油站 i 与起点的距离 D_i 和每单位汽油价格 P_i。你需要求出最小的费用。

数据范围：0\red{\le}N\le6，0\red{\le}S,C,L\le500，0\red{\le}P_i\le500，0\red{\le}D_i\le S。

2. 题目讲解

看到题意，考虑反悔贪心。

由于你现在是 2026 年，你的油箱非常智能，可以把油按售价自动分层。并且你可以随时把其中一部分油瞬间邮寄回去，商家非常良心，会给你退款。

注（可以这样的原因）：当你按照这套流程（在脑子里）走完一遍后，你可以记录你在每个油站实际使用了多少油，然后重新走一遍，每次只买需要的油，就是最优解。

现在，考虑让你在行驶时会优先消耗便宜的油。这很好理解，因为更贵的油可以先存着，说不定还可以把它邮寄回去。（用了的油就寄不回去了喵）

每次到达一个油站，使用类似单调队列的结构维护油箱。具体方案如下：

恭喜你，你已经知道了这道题的完整思路。虽然我不会算复杂度，但由于 N\le6，你就算玩出花来也不可能 TLE。

小 Tricks：

  1. 把起点也当成一个油站，编号为 0，满足 D_0=0（P_0 已输入）。
  2. 与上一条类似，把终点也当成一个油站，编号为 N+1，满足 D_{N+1}=S，P_{N+1}=0。P_{N+1}=0 的原因：结合前面的流程，由于此时终点的售价一定是最便宜的，前面所有多余的油都会被邮寄回去，与终点在同一位置的油站也不可能把终点买的油顶掉。

注意：

  1. 记得把油站按距离排序。
  2. 浮点数计算有误差，一定要用 eps 判断。（所有涉及浮点数计算的题都要记住这一点）

3. AC 代码

:::success[AC 代码]

#include <iostream>
#include <algorithm>
#include <queue>
typedef long long longlong;
// #define int longlong
using namespace std;

const int N = 10;
const double eps = 1e-6;
int n;
double s, c, l;

struct node1{
    double d, p;

    node1(double d = 0, double p = 0){
        this->d = d, this->p = p;
    }
} a[N];

bool operator<(node1 a, node1 b){
    return a.d < b.d;
}

struct node2{
    double p, m; // p=油价 m=油量

    node2(double p = 0, double m = 0){
        this->p = p, this->m = m;
    }
}; deque<node2> q;

signed main(){
    // freopen("ceshi.in", "r", stdin);
    // freopen("ceshi.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    cin >> s >> c >> l >> a[0].p >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].d >> a[i].p;
    }
    a[n + 1] = node1(s, 0);
    sort(a, a + n + 2);
    double pos = 0, sum = 0, ans = 0;
    for (int i = 0; i <= n + 1; i++){
        #define frt q.front()
        #define bck q.back()
        while (!q.empty() && a[i].d - pos > eps){
            if (pos + frt.m * l - a[i].d > eps){
                frt.m -= (a[i].d - pos) / l, sum -= (a[i].d - pos) / l, pos = a[i].d;
            }
            else{
                sum -= frt.m, pos += frt.m * l;
                q.pop_front();
            }
        }
        if (a[i].d - pos > eps){
            cout << "No Solution";
            return 0;
        }
        pos = a[i].d;
        while (!q.empty() && a[i].p - bck.p < eps){
            sum -= bck.m, ans -= bck.m * bck.p;
            q.pop_back();
        }
        ans += a[i].p * (c - sum);
        q.push_back(node2(a[i].p, c - sum));
        sum = c;
        #undef frt
        #undef bck
    }
    printf("%.2f", ans);
    return 0;
}

:::