优先队列 POJ 2431 Expedition

题目传送门

题意：一辆卡车要行驶L长度，初始有P油，每行驶一个单位长度消耗一单位油。有n个加油站可以加油，问最少加油几次才能行驶L长度，如果不能输出-1

分析：按照挑战书的解法，每走到一个加油站相当于获得一次加油的权利，等到油没有的时候再选择之前可加油的站的最大油量加上，可以用优先队列高效得到最大值，如果队列里没油使得继续前进则为-1

收获：换一种思考方式，加上高效的数据结构能完美解决难题

代码：

/************************************************
* Author        :Running_Time
* Created Time  :2015/9/14 星期一 08:28:25
* File Name     :POJ_2431.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
struct Oil  {
    int p, v;
    bool operator < (const Oil &r) const {
        return p < r.p;
    }
}o[N];

int main(void)    {
    int n;
    while (scanf ("%d", &n) == 1)   {
        int L, P;
        for (int i=n; i>=1; --i)    scanf ("%d%d", &o[i].p, &o[i].v);
        scanf ("%d%d", &L, &P);
        for (int i=n; i>=1; --i)    o[i].p = L - o[i].p;        //起点到加油站的距离
        o[++n].p = L; o[n].v = 0;
        sort (o+1, o+1+n);
        priority_queue<int> Q;
        int ans = 0, pos = 0;
        for (int i=1; i<=n; ++i)    {
            int d = o[i].p - pos;
            P -= d;
            while (P < 0)   {
                if (Q.empty ()) {
                    ans = -1;   break;
                }
                P += Q.top ();  Q.pop ();
                ans++;
            }
            if (ans == -1)  break;
            pos = o[i].p;
            Q.push (o[i].v);
        }
        printf ("%d
", ans);
    }

    return 0;
}