优先队列的使用（poj2431）

感觉这种题目就是需要一种思想，就是在什么情况下需要使用优先队列。目前来说，感觉使用这种数据结构的话，题目一般都是需要通过选择最大/最小的几个数，计算出最终结果。那么使用优先队列的话，可以更快的找出那几个数。

题目大概意思就是，你要开车去L公里外的城镇，你现在车上的油还能走p公里。沿途有很多加油站，每个加油站都能让你加能够走m公里的油，试问最少加多少次油，就能到达城镇。

这个题目我们思考后会发现，每经过一个加油站，就认为获得了一次的加油机会，在今后没油的时候，可以使用之前已经拥有的加油机会。这样子问题就好办了，我们只要在没油的时候就加油，并且使用以前的最大的一次的加油机会，就可以了。要是把之前的所有机会用完都不能到达，那就输出-1

代码：

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

#define MAXN 10004

struct fuel_stop
{
    int dis, amount;
} fs[MAXN];

bool cmp(const fuel_stop &a, const fuel_stop &b)
{
    return a.dis>b.dis;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, l, p;
    cin >> n;
    for(int i=0;i<n;++i)
    {
        cin>>fs[i].dis>>fs[i].amount;
    }
    fs[n].amount=0,fs[n].dis=0;
    sort(fs,fs+n+1,cmp);
    cin>>l>>p;

    priority_queue<int> pq;
    int last_distance = l;
    int js=0;
    for(int i=0;i<=n;++i)
    {
        if(last_distance - fs[i].dis-p>0)
        {
            while(!pq.empty()&&last_distance - fs[i].dis-p>0)
            {
                ++js;
                p+= pq.top();
                pq.pop();
            }
            

            if(last_distance - fs[i].dis-p>0)
            {
                
                cout<<-1<<endl;
                return 0;
            }
        }
        
        p -= last_distance - fs[i].dis;
        last_distance = fs[i].dis;
        
        pq.push(fs[i].amount);
    }
    cout<<js<<endl;
    return 0;
}

转载请注明来源：https://www.longjin666.top/?p=1116

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~