[POJ 2431]Expedition

若現在卡車能跑到某個距離，那麼能加油的地方只能在這個距離裡面
要在哪裡加油呢？
在哪裡加油都沒差，唯一的差別就是能讓你多跑多少公里
就選一個加最多油的加油站加油吧
然後繼續跑，跑不到終點的話再繼續選一個距離內加最多油的加油站

可以用priority_queue維護加最多油的加油站

如果最後沒有加油站可以選惹，輸出-1

時間複雜度：$O(N\log N)$

code:

#include<cstdio>
#include<cassert>
#include<queue>
#include<algorithm>
using namespace std;
struct FuelStop
{
    int dist,fuel;
    bool operator<(const FuelStop &f)const{return dist<f.dist;}
}STOP[10000];
int N,L,P;
int Solve()
{
    priority_queue<int>pq;
    int ans=0,dist=P,cur=0;
    while(dist<L)
    {
        while(cur<N&&STOP[cur].dist<=dist)pq.push(STOP[cur++].fuel);
        if(pq.empty())return -1;
        dist+=pq.top(),ans++,pq.pop();
    }
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)scanf("%d%d",&STOP[i].dist,&STOP[i].fuel);
        scanf("%d%d",&L,&P);
        for(int i=0;i<N;i++)STOP[i].dist=L-STOP[i].dist;
        sort(STOP,STOP+N);
        printf("%d\n",Solve());
    }
    return 0;
}