POJ 2431-Expedition

题意：

开车前往一个距离为l的城市，途中有n个加油站，每行驶一个单位的距离就会消耗一个单位的汽油，每到一个加油站都可以加油，问是否能到达目的地，能到达的话，最少需要加多少次油。

思路：

衷心提醒大家仔细看题！！！！！！
输入的距离不是距起点的距离，而是距终点的距离(白WA3发血亏），而且不一定按顺序给出，需要进行排序，所以用结构体还是比较方便的。

我们可以这样想，既然路过的每个加油站都可以加油，意思就是“经过一个加油站就获得了在之后任何一个时间加油的权力”。
为了最小化加油的次数，我们只有在必须加油的时候才加油，并且加油的量应该是途径的所有加油站的可加油量的最大值。那么什么时候是必须加油的时候呢？
显然 当前油箱里的油不够前往下一个加油站时我们必须加油，且应该选加油量最大的加油站加油
所以我们用优先队列存储我们经过的所有加油站的可加油量，问题即可得解。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl &#39;\n&#39;

using namespace std;
typedef long long ll;
const int maxn = 2e4 + 10;
struct node {
   
    int dis, u;
}sta[maxn];

bool cmp(node a, node b) {
   
    return a.dis < b.dis;
}

int main()
{
   
    int n;cin >> n;

    for (int i = 1;i <= n;++i) {
   
        int x, y;cin >> x >> y;
        sta[i].dis = x;//距终点的距离
        sta[i].u = y;//可加油的量
    }

    int l, p;cin >> l >> p;

    //求加油站到起点的距离
    for (int i = 1;i <= n;++i) {
   
        sta[i].dis = l - sta[i].dis;
    }

    sort(sta + 1, sta + n + 1, cmp);//排序

    //将终点看成最后一个不能加油的加油站
    sta[n + 1].dis = l;
    sta[n + 1].u = 0;

    priority_queue<int>pq;

    int ans = 0;//加油次数
    int pos = 0;//当前位置
    int oil = p;//油箱里的油

    for (int i = 1;i <= n + 1;++i) {
   
        //前往下一个加油站的距离
        int t = sta[i].dis - pos;
        //油量不够时，从优先队列中加油
        while (t > oil) {
   
            //如果在途中优先队列为空 说明无法到达目的地
            if (pq.empty()) {
   
                puts("-1");
                return 0;
            }
            oil += pq.top();
            pq.pop();
            ++ans;
        }
        oil -= t;
        pos = sta[i].dis;
        pq.push(sta[i].u);//获得可加油的权力
    }

    printf("%d\n", ans);
    return 0;
}