题解 | 旅行家的预算-NOIP1999普及组复赛C题

#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;
}