[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
查看45道真题和解析
