poj 2431 Expedition 贪心

简单的说说思路,如果一开始能够去到目的地那么当然不需要加油,否则肯定选择能够够着的油量最大的加油站加油,,不断重复这个贪心的策略即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1e4+9;
int dist,p,n;
struct S
{
int d,f;
bool operator <(const S & xx) const
{
return d<xx.d;
}
}stop[maxn]; struct cmp
{
bool operator ()(const S &a,const S &b) const
{
return a.f<b.f;
}
}; int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d %d",&stop[i].d,&stop[i].f);
scanf("%d %d",&dist,&p);
for(int i=1;i<=n;i++)
stop[i].d=dist-stop[i].d;
sort(stop+1,stop+1+n); int ans=0,t=1;
bool flag=true;
priority_queue <S,vector<S>,cmp> q;
while(p<dist)
{
while(t<=n&&stop[t].d<=p) q.push(stop[t++]);
if(q.empty())
{
flag=false;
break;
}
ans++;
p+=q.top().f;
q.pop();
}
if(flag) cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}
上一篇:poj - 2431 Expedition (优先队列)


下一篇:POJ 2431 Expedition (贪心 + 优先队列)