poj 3431 Expedition 优先队列

题目链接：

http://poj.org/problem?id=2431

思路：

优先队列。对于一段能够达到的距离，优先选择其中能够加油最多的站点，这样，行驶过这段距离之后还能走更远的距离。

将输入的数据进行排序处理，按照位置的先后。注意输入的距离是与终点的，要转化成与起点的。

代码：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <queue>

using namespace std;

const int maxn = 10005;

struct node {

    int a,b;

} ans[maxn];

bool cmp(const node& x, const node& y) {return x.a<y.a;}

priority_queue<int,vector<int>,less<int> > q;

int main() {

    int n,l,p;

    scanf("%d",&n);

    for(int i=0;i<n;++i) scanf("%d %d",&ans[i].a,&ans[i].b);

    scanf("%d %d",&l,&p);

    for(int i=0;i<n;++i) ans[i].a=l-ans[i].a;

    ans[n].a=l;

    ans[n].b=0;

    n++;

    sort(ans,ans+n,cmp);

    int index=0,last=p,cnt=0;

    for(int i=0;i<n;++i) {

        int dist=ans[i].a-index;

        while(dist>last) {

            if(q.empty()) {

                puts("-1\n");

                return 0;

            }

            last+=q.top();

            q.pop();

            cnt++;

        }

        last-=dist;

        index=ans[i].a;

        q.push(ans[i].b);

    }

    printf("%d\n",cnt);

    return 0;

}