[PAT解题报告] To Fill or Not to Fill

经典问题，汽车加油问题，从起点到终点，有若干个加油站，每个加油站油价不同，汽车油箱容积有限，问能否到终点，如何最便宜。

可以贪心，我比较喜欢的做法。到当前加油站，就把油箱加满。我们把油箱里的油看成是“分块”的，每块油有自己的价钱。我们使用油的时候从最便宜的开始用。加油的时候，如果当前加油站的油比邮箱里的还没用的油便宜，就把贵的油换掉。

所以油箱里的油可以存储为这样的pair, (价钱，油量) ，到达一个加油站，就把所有油价比它贵的油用这个加油站的油换掉，所以离开加油站的时候，油箱总是满的，使用的时候先用最便宜的油。注意：最后没有使用的油是不算钱的，可以理解为我们把油退回去。所以只有真正使用的油，才算钱，加油时，并不算钱。

那么这个油箱其实可以使用一个队列存所有的pair。这个队列自然单调的，比如，我们可以维从队头到队尾的油逐渐变贵。那么我们使用的时候，从队头的油开始用，加油的时候，看一下如果队尾的油比当前加油站贵，就从队尾把油弹出来，不断弹出来，最后再用当前加油站的油加满。所以当前加油站的油比邮箱里存下的油贵，但是对于要换掉的油，它是便宜的，我们用便宜的油换了贵的油。

所以时间复杂度是O(n)的……

另外一点你要注意的是，浮点数比较大小最好使用eps，这点比较讨厌。

代码：

#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm>

using namespace std;

const double eps = 1.e-8;
pair<double, double> g[505];

deque<pair<double,double> >  q;

int main() {
int n;
double tank, dis, avg;

    scanf("%lf%lf%lf%d",&tank, &dis, &avg, &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lf%lf",&g[i].second, &g[i].first);
    }
    g[n++] = make_pair(dis, 0.);
    sort(g, g + n);
    double cost = 0., now = 0., oil = 0.;
    for (int i = 0; (i < n) && (now + eps <= dis); ++i) {
        double d = g[i].first - now;
        while ((!q.empty()) && (d >= eps)) {
            double need = d / avg;
            if (q.front().second < need + eps) {
                double temp = q.front().second * avg;
                now += temp;
                cost += q.front().second * q.front().first;
                oil -= q.front().second;
                d -= temp;
                q.pop_front();
            }
            else {
                now += d;
                cost += need * q.front().first;
                q.front().second -= need;
                oil -= need;
                d = 0.;
            }
        }
        if (d >= eps) {
            break;
        }
        while ((!q.empty()) && (q.back().first >= g[i].second + eps)) {
            oil -= q.back().second;
            q.pop_back();
        }
        if (oil + eps <= tank) {
            q.push_back(make_pair(g[i].second, tank - oil));
            oil = tank;
        }
    }
    if (now + eps > dis) {    
        printf("%.2lf\n",cost);
    }
    else {
        printf("The maximum travel distance = %.2lf\n",now);
    }
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1033