首页 > 代码库 > poj2431 Expedition

poj2431 Expedition

直接代码、、、

#include<string.h>
#include<stdio.h>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int fuel,dist;
    //bool operator < (const node&d) const{
     // return  dist>d.dist;
   // }
}s[10005];
bool cmp(node b,node c)
{
    return b.dist>c.dist;
}
int main()
{
    int a,l,p,pos,ans,d,fuels;
    scanf("%d",&a);
    priority_queue<int> q;
    for(int i=0;i<a;i++)
    {
        scanf("%d %d\n",&s[i].dist,&s[i].fuel);
    }
    sort(s,s+a,cmp);//从大到小进行排序,
    scanf("%d %d",&l,&p);
    s[a].dist=0;
    for(int i=0;i<=a;i++)
        s[i].dist=l-s[i].dist;
    fuels=p;
    ans=0;
    pos=0;
    for(int i=0;i<=a;i++)
    {
        d=s[i].dist-pos;
        while(fuels-d<0)
        {
            if(q.empty())
            {
                printf("-1\n");
                return 0;
            }
            fuels+=q.top();
            q.pop();
            ans++;
        }
        fuels-=d;
        pos=s[i].dist;
        q.push(s[i].fuel);
    }
    printf("%d\n",ans);
    return 0;
}