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

题目: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

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

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注