POJ2431 Expedition(排序+优先队列)

时间:2023-03-09 09:51:05
POJ2431 Expedition(排序+优先队列)

思路:先把加油站按升序排列。

在经过加油站时。往优先队列里增加B[i].(每经过一个加油站时,预存储一下油量)

当油箱空时:1、假设队列为空(能够理解成预存储的油量),则无法到达下一个加油站,更无法到达目的地。

2、否则就取出队列里的最大元素,来给汽车加油(贪心思想)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; int n,l,p;
int t[10005];
struct Node
{
int a,b;
bool operator < (const Node e)const
{
return e.a>a;
}
}s[10005];
int B[10005];
int A[10005]; int main()
{
//freopen("d:\\test.txt","r",stdin);
cin>>n;
priority_queue<int>q;
for(int i=0;i<n;i++)
{
scanf("%d%d",&t[i],&s[i].b);
}
cin>>l>>p;
for(int i=0;i<n;i++)
{
s[i].a=l-t[i];
}
sort(s,s+n);
for(int i=0;i<n;i++)
{
A[i]=s[i].a;
B[i]=s[i].b;
}
A[n]=l;B[n]=0;
int pos=0,fuil=p,ans=0;
for(int i=0;i<=n;i++)
{
int d=A[i]-pos;
while(fuil<d)
{
if(q.empty()) {cout<<"-1";return 0;}
fuil+=q.top();
q.pop();
ans++;
}
fuil-=d;
pos=A[i];
q.push(B[i]);
}
cout<<ans<<endl;
return 0;
}