POJ2431 Expedition (优先队列)

题目链接：

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

题意：

一条路上有n个加油站，终点离起点的距离为L，然n个加油站离终点的距离为a[i],每个加油站可以给汽车加b[i]的油，

问最少加多少次可以到达终点，不能到达终点输出-1。

分析：

要想最少我们肯定是在马上要没有的时候加油，然后每次加的应该是最多的油。

因此我们走过第i个加油站的时候，把b[i]放入优先队列里，然后不能到达的时候

每次取出一个直到可以到达当前的位置，如果队列为空而且还不能动到达当前

位置则永远不可达。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn = 1000010;

struct stop {
    int a,b;
    bool operator <(const struct stop &tmp)const {
        return a<tmp.a;
    }
} p[maxn];

int n,l,pp;

void solve()
{
    p[n].a=l,p[n].b=0;
    sort(p,p+n+1);
    int tot = pp;
    priority_queue<int >Q;
    while(!Q.empty()) Q.pop();
    int ans = 0,pos=0,tag=0;
    for(int i=0; i<=n; i++) {
        int dis = p[i].a-pos;
        while(tot<dis) {
            if(Q.empty()) {
                printf("-1\n");
                return;
            }
            tot+=Q.top();
            Q.pop();
            ans++;
        }
        tot-=dis;
        pos=p[i].a;
        Q.push(p[i].b);
        //printf("tot: %d\n",tot);
    }
    printf("%d\n",ans);
    return ;
}
int main()
{
    while(~scanf("%d",&n)) {
        int a,b;
        for(int i=0; i<n; i++)
            scanf("%d%d",&p[i].a,&p[i].b);
        scanf("%d%d",&l,&pp);
        for(int i=0; i<n; i++)
            p[i].a=l-p[i].a;
        solve();
    }
    return 0;
}
/***
4
4 4
5 2
11 5
15 10
25 10
***/

POJ2431 Expedition (优先队列)

原文：http://blog.csdn.net/bigbigship/article/details/42239591