旅行家的预算 NOIP1999 （洛谷P1016） 题解

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，…，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入输出格式

输入格式：

第一行，D1，C，D2，P，N。

接下来有N行。

第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。

输出格式：

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。

输入输出样例

输入样例#1：

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出样例#1：

26.95

说明

N≤6，其余数字≤500

解题思路

这题我采取的方法是模拟车在加油站之间行驶的过程，使过程中需要用的每一份油都使用能够使用的最便宜的油。这种想法比较抽象，难以理解，不过清晰并且实现起来容易。题解中会有分析和举例帮助理解。

首先说一下怎么做到“使过程中需要用的每一份油都使用能够使用的最便宜的油”。我们不断地维护可用的“燃油提供者”（即加油站）的列表。等到要用油的时候，再从列表中选取最便宜的油拿来用，而不是在到那个油站的时候就决定好加多少油。我们设想现在正打算从加油站G1行驶到G2，模拟选取最优的过程。这个过程需要讨论，细节如下：

• 从当前可用的“提供者”中选取最便宜的备用
• 计算从G1行驶到G2所需的油量，并且从“提供者”处买来燃油，加进车的油箱里
• 将车从G1开到G2，再以G2为起点计算下一步的行动

可以容易得出以下的结论：

1. 每个加油站最多能给你加一油箱的油，如果加的更多油箱装不下
2. 只有到现在所在位置的距离小于一油箱油能够行驶的距离，在这样的加油站才能买油（实际情况是如果超出这一距离，等你到这个位置之前一油箱的油就被用完了，这些油包括了你在那个很远的油站买的油）

需要讨论的内容：

• 如果最便宜油站到现在所在位置的距离在一油箱油能够行驶的距离之内，且这个油站还可以买够从G1到G2所需的油，那很好，直接把这些油买下来
• 如果最便宜油站到现在所在位置的距离在一油箱油能够行驶的距离之外，或这个油站不能继续买油了，把它从列表中删去
• 如果最便宜油站到现在所在位置的距离在一油箱油能够行驶的距离之内，且这个油站买不够从G1到G2所需的油，选择次便宜的买够，若仍不够，循环操作

以题目样例为例：

实现上，列表用堆/优先队列维护，可以将起点、终点作为油站加入列表，走到终点结束前进即可。实现代码中有详细注释。

实现代码

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct gas {
    double pos, price, vol;
} g[505];

bool cmp(gas a, gas b) {
    return a.pos < b.pos;
} 

struct cmp1 {
    bool operator()(int a, int b) {
        return g[a].price > g[b].price;
    }
};

priority_queue<int, vector<int>, cmp1> pq; // 堆存可以用的油 

int n; // 注意n可以为0 
double dis, vol, doil, sprice, maxdis;

int main() {
    scanf("%lf%lf%lf%lf%d", &dis, &vol, &doil, &sprice, &n);
    maxdis = vol * doil;
    if(n == 0) { // 对n为0的特判 
        if(dis > maxdis) {
            printf("No Solution");
        } else {
            printf("%.2lf", dis / doil * sprice);
        }
        return 0;
    }
    // 把起点和终点都加入加油站的列表 
    g[0].pos = 0, g[0].price = sprice, g[0].vol = 0;
    g[n + 1].pos = dis, g[n + 1].price = -1, g[n + 1].vol = -1;
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf", &g[i].pos, &g[i].price);
        g[i].vol = 0;
    }
    sort(g, g + n + 1, cmp); 
    pq.push(0);
    int ngas = 0; // 表示现在开到了下表为ngas的加油站 
    double ncost = 0; // 表示现在的累计花费油钱 
    while(ngas < n + 1) {
        //printf("maxdis %lf dis %lf\n", maxdis, g[ngas].pos - g[pq.top()].pos);
        // 如果走的太远远处的油站就无法加油了，或是这个油站已经买了一箱油没办法再加了，这两种情况要把油站出堆 
        while(g[ngas].pos - g[pq.top()].pos > maxdis || g[pq.top()].vol >= vol) {
            pq.pop(); 
        } 
        // 无解的情况：存在相邻油站距离大于一箱油可以支持的距离 
        if(g[ngas + 1].pos - g[ngas].pos > maxdis) {
            printf("No Solution");
            return 0;
        }
        int gmin = pq.top();
        pq.pop();
        //printf("ngas %d ncost %lf gmin pos %lf price %lf vol %lf\n", ngas, ncost, g[gmin].pos, g[gmin].price, g[gmin].vol);
        double gcost = (g[ngas + 1].pos - g[ngas].pos) / doil;
        // 往前走一个油站，计算这段路程的油费开支 
        if(vol - g[gmin].vol >= gcost) { // 如果最便宜的油能够支持这一段路程 
            ncost += gcost * g[gmin].price;
            g[gmin].vol += gcost;
        } else { // 如果最便宜的油不能支持这一段路程，那么就要补充次便宜的 
            while(gcost > 1e-10) { // EPS设为1e-10避免浮点陷阱 
                double navailable = vol - g[gmin].vol; // 现在选择的油站可以买的油量 
                ncost += min(gcost, navailable) * g[gmin].price;
                gcost = max(1e-10, gcost - navailable);
                g[gmin].vol = min(vol, g[gmin].vol + gcost); 
                while(g[ngas].pos - g[pq.top()].pos > maxdis || g[pq.top()].vol >= vol) {
                    pq.pop(); 
                }
                gmin = pq.top();
            }
        }
        ngas++;
        pq.push(gmin); // 把还能加的油加进去 
        pq.push(ngas);
    }
    printf("%.2lf", ncost);
    return 0;
}