2016年2月15日 星期一

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原