codility上的问题之九 Theta 2011

时间:2022-11-16 00:00:19

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