POJ2431_Expedition_KEY

题目传送门

由题目可得，在一条路上有N个加油站，在距离终点a[i](细节)的位置上，你需要通过长度为L的路，油箱的容量是无限的，但是初始只有P点油，经过每个加油站时可以选择加b[i]的油，问最少加油几次可以到达终点。

可以看出经过每一个加油站时可以有两个选择：加油或不加油，但过去了就不能回来。

假如我们就要没油了，我们是不是这样想：我当时应该在XX加油站加油才对。

所以，我们假设我们可以时空穿梭，回到经过XX加油站的时候，立即加油。

开一个堆记录经过的、未加油的加油站。

在即将没油时从堆里拿出油多的加油站加油，直到又有油可以到达下一个加油站。

这里有一个细节，要再设置一个在终点的、油量为0的加油站。

code：

#include <cstdio>

#include <cctype>

#include <algorithm>

#include <queue>

using namespace std;

inline char getch(){

    static char fl[],*A=fl,*B=fl;

    return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;

}

inline int read(){

    char c;

    while(!isdigit(c=getch()));int x=c-'';

    while(isdigit(c=getch()))x=x*+c-'';

    return x;

}

int L,P,i,now,ans;

struct node{

    int x,y;

}a[];

inline int cmp(node x,node y){return x.x<y.x;}

int main(){

    int N;

    while(~scanf("%d",&N)){

        for(i=;i<=N;i++)a[i].x=read(),a[i].y=read();

                L=read(),P=read();

                for(i=;i<=N;i++)a[i].x=L-a[i].x；

        a[++N].x=L;priority_queue<int>w;

        sort(a+,a+N+,cmp);

        for(i=;i<=N;i++){

            int cost=a[i].x-now;

                while(P<cost){

                    if(w.empty()){puts("-1");return ;}

                    P+=w.top(),w.pop(),ans++;

                }

            w.push(a[i].y);

            now=a[i].x,P-=cost;

        }

    printf("%d\n",ans);

    }

}