codility上的问题描述是在过于复杂，我自己化简了。不过读题确实是一项技巧啊。汽车加油问题，经过N个点，有（N+1）个城市，0是起点, N是终点。两个数组长度为N，D[0..N-1]表示第i个城市到下一个城市的距离,P[0..N - 1]表示第i个城市的油价。汽车单位距离耗油也是1个单位，油箱容积是Ｔ，问汽车从0到(N+1)最少花费？
数据范围：
Ｎ １..10^5
T ,D , P种的元素都是 1..10^6
如果无法到达终点 输出-1
如果到达终点花费超过10^9，输出-2
要求复杂度 时间O(N), 空间O(N)。
分析： 汽车加油问题。我们可以从一个城市离开时把油加满，但“暂时不付钱”。我们可以认为油箱里的油是“分块”的，即按照由便宜到贵的顺序，分别是（p1, m1), (p2, m2)...m是数量，所有m之和等于T，p是价格排好序的。我们去一个城市的时候，使用尽可能便宜的油，也就是说从开头使用油。而我们到达城市加满油时，如果发现这个地方的油比之前加的便宜，则把之前加的没有使用的油换掉，即从这个表的后面把油换掉。这样这个表永远是有序的。复杂度的话，这个表的长度最多是N，每个点最多出入一次，所以是O(N)的。这个表可以用双端队列来实现，我用的是stl里的list（双向链表）。还有要注意如果目前花费已经超过10^9 不能立刻输出-2，因为还不一定有解。当然可以先扫一遍D，判断一下是否有解的，不过我没那么做。
代码：
// you can also use includes, for example:
// #include <algorithm>
#include <list>
int solution(const vector<int> &D, const vector<int> &P, int T) {
// write your code here...
list<pair<int,int> > have;
int cost = 0, d, i,fuel;
bool exceed = false;
for (i = 0; i < D.size(); ++i) {
for (; (!have.empty()) && (have.back().first >= P[i]); have.pop_back()) {
T += have.back().second;
}
if (T) {
have.push_back(make_pair(P[i], T));
T = 0;
}
for (d = D[i]; (!have.empty()) && d;) {
fuel = min(d, have.front().second);
d -= fuel;
T += fuel;
if ((!exceed) && ((1000000000 - cost) / have.front().first < fuel)) {
exceed = true;
}
else {
cost += have.front().first * fuel;
}
if ((have.front().second -= fuel) == 0) {
have.pop_front();
}
}
if (d) {
return -1;
}
}
return exceed?(-2):cost;
}