POJ2431 優先隊列+貪心

題目大意：

見《挑戰程式設計競賽》P74。

我的了解：

優先隊列+貪心

注意把輸入的距離（加油站到終點）改為起點到加油站。

#include<iostream>
#include<queue>
using namespace std;
const int maxn = 10000 + 10;

typedef pair<int, int> P;
int L, p, N;
P stop[maxn];

int cmp(P p1, P p2) {
    return p1.first < p2.first;
}

void solve() {
    //技巧
    stop[N].first = L;
    stop[N].second = 0;
    N++;
    priority_queue<int> que;
    int ans = 0, pos = 0, tank = p;
    for (int i = 0; i < N; i++) {
        int d = stop[i].first - pos;
        while (tank - d < 0) {
            if (que.empty()) {
                puts("-1");
                return;
            }
            tank += que.top();
            que.pop();
            ans++;
        }
        tank -= d;
        pos = stop[i].first;
        que.push(stop[i].second);
    }
    cout << ans << endl;
}


int main()
{
    //freopen("in.txt", "r", stdin);
    while (scanf("%d", &N) != EOF) {
        for (int i = N - 1; i >= 0; i--) {
            cin >> stop[i].first >> stop[i].second;
        }
        cin >> L >> p;
        for (int i = 0; i < N; i++) {
            stop[i].first = L - stop[i].first;
            //cout<<A[i]<<" "<<B[i]<<" ";
        }
        sort(stop, stop + N, cmp);
        solve();
    }
    return 0;
}