HIT 2051

这题说的是 一辆汽车 每走一单位的距离就消耗一单位的燃料，然后，他要回城里去，当然他与城镇之间有n个加油站 ，他的油箱可以为 无穷大 ，这样分析后发现进不进汽油站 与 汽油站在哪无关 ，只与加油站的 汽油有关 （当然是他能到达的加油站）然后直接贪心

#include<string.h>

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

struct point {

    int dist,pow,num;

    bool operator <(const point &b) const{

       if(pow<b.pow) return true;

       else return false;

    }

};

point P[100005];

bool cmp(point a,point b)

{

    if(a.dist>b.dist) return true;

    else return false;

}

bool mark[100005];

int main()

{

   int i,n,num;

   point T,W;

   priority_queue<point>Q;

   while(scanf("%d",&n)==1){

       while(!Q.empty())Q.pop();

        num=0;

        memset(mark,true,sizeof(mark));

        for(i=0;i<n;i++)

        scanf("%d%d",&P[i].dist,&P[i].pow);

        sort(P,P+n,cmp);

        scanf("%d%d",&T.dist,&T.pow);

        for(i=0;i<n;i++)

        P[i].num=i;

		T.num=-1;

        Q.push(T);

        while(!Q.empty()){

            Q.pop();

            if(T.pow>=T.dist) break;

            for(i=T.num+1;i<n;i++)

              if(T.pow-(T.dist-P[i].dist)>=0&&mark[i]){

                  Q.push(P[i]);

                  mark[i]=0;

              }

              if(Q.empty()) break;

              W=Q.top();

            if(W.dist>T.dist){

               T.pow+=W.pow;

            }

            else{

                 W.pow+=T.pow-(T.dist-W.dist);

                 T=W;

            }

             num++;

            if(T.pow>=T.dist) break;

        }

        if(T.pow>=T.dist)printf("%d\n",num);

        else printf("-1\n");

   }

    return 0;

}