优先队列的使用（poj2431）
感觉这种题目就是需要一种思想，就是在什么情况下需要使用优先队列。目前来说，感觉使用这种数据结构的话，题目一般都是需要 通过选择最大/最小的几个数，计算出最终结果。那么使用优先队列的话，可以更快的找出那几个数。
题目：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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021年8月16日2，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
