Expedition [POJ2431] [贪心]

题目大意：

有n个加油站，每个加油站的加油的油量有限，距离终点都有一个距离。

一个卡车的油箱无限，每走一个单元要消耗一单元的油，问卡车到达终点的最少加多少次油。

分析：

我们希望的是走到没油的时候就尽可能加更多的油

显然我们是没办法随时获得加油的机会的

但是我们把我们走过的加油站全按从大到小记下来

没有了就加，如果加油站全都用完了，就代表gg了，puts("-1")

代码：

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define ll long long

 #define maxn 10005

 #define rep(i,a,b) for(RG i=a;i<=b;i++)

 #define per(i,a,b) for(RG i=a;i>=b;i--)

 using namespace std;

 int n,f,d,ans,pos,fuel;

 int F[maxn],D[maxn];

 struct Dat{

     int F,D;

     bool operator < (const Dat &a)const{

         return D<a.D;

     }

 }dat[maxn];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 priority_queue<int> que;

 int main()

 {

     n=read();

     rep(i,,n)    dat[i].D=read(),dat[i].F=read();

     d=read(),f=read();

     rep(i,,n)    dat[i].D=d-dat[i].D;

     dat[++n].D=d,dat[n].F=;

     sort(dat+,dat++n);

     fuel=f;

     rep(i,,n)

     {

         int dis=dat[i].D-pos;

         while(dis>fuel)

         {

             if(que.empty())

             {

                 puts("-1");return ;

             }

             ans++;

             fuel+=que.top();que.pop();

         }

         fuel-=dis;

         pos=dat[i].D;

         que.push(dat[i].F);

     }

     cout<<ans;

     return ;

 }