[POJ] 2431 Expedition.cpp

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct fuel_stop{
    int pos;
    int amount;
}stop[10010];
bool cmp(fuel_stop a, fuel_stop b)
{
    return a.pos > b.pos;
}
int main()
{
    int N, L, P;
    while (scanf("%d", &N) != EOF) {
        for (int i = 0; i < N; ++i)
            scanf("%d %d", &stop[i].pos, &stop[i].amount);
        scanf("%d %d", &L, &P);

        sort(stop, stop + N, cmp);

        stop[N] = {0,0};  // 終點也當一個stop
        priority_queue<int> PQ;  // PQ用來裝每個stop的油量

        int dis = L - stop[0].pos;  // 起點~第一站
        int sum_dis = dis;          // 總共已經走了多遠
        P -= dis;

        int i = 0;    // i用來當index
        int ans = 0;
        bool OK = 1;
        while (sum_dis < L && OK) {
            while (P >= 0) {   //當身上油還>=0時繼續前進
                dis = stop[i].pos - stop[i+1].pos;
                P -= dis;
                sum_dis += dis;
                PQ.push(stop[i].amount);
                ++i;
                if (i == N) break;
            }
            while (P < 0 && OK) {  // PQ裡面從最多油量開始挑,加入油箱
                if (PQ.empty()) OK = 0;
                else{
                    P += PQ.top();
                    PQ.pop();
                    ++ans;
                }
            }
        }
        if (OK) printf("%d\n", ans);
        else puts("-1");
    }
}