codility上的问题描述是在过于复杂,我自己化简了。不过读题确实是一项技巧啊。汽车加油问题,经过N个点,有(N+1)个城市,0是起点, N是终点。两个数组长度为N,D[0..N-1]表示第i个城市到下一个城市的距离,P[0..N - 1]表示第i个城市的油价。汽车单位距离耗油也是1个单位,油箱容积是T,问汽车从0到(N+1)最少花费?
数据范围:
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; }