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;  
}

补充：软件开发 , C++ ,