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