codility.com 2011Theta_gas_station

2011_theta_gas_station.cc

// 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> > tank; //油箱里面都装了些什么油,由便宜到贵排序的
    int curr = 0;
    long long cost = 0;
    for (int i = 0; i < D.size(); ++i) {
        while (!tank.empty() && P[i] < tank.back().first) { //油箱里面有比这个加油站还贵的油, 全部扔掉
            curr -= tank.back().second;
            tank.pop_back();
        }
        tank.push_back( pair<int, int>(P[i], T - curr) ); //装满油箱
        curr = T;
        long long need = D[i];
        while (need && !tank.empty()) { //先用便宜的油
            if (tank.front().second > need) {
                cost += need * tank.front().first;
                tank.front().second -= need;
                curr -= need;
                need = 0;
            } else {
                cost += 1LL * tank.front().second * tank.front().first;
                curr -= tank.front().second;
                need -= tank.front().second;
                tank.pop_front();
            }
        }
        if (need > 0) {
            return -1;
        }
        if (cost > 1e9) {
            return -2;
        }
    }
    return cost;
}