[POJ 2431][Heap] Expedition

原題連結
出乎意料單純的一道題......
觀察到，假設我們現在所能到的最遠距離為d，想要再更往前時，我們應該會最優先去加哪個加油站的油呢？

答案很顯然就是：在d之內有最多油的加油站。

有了這個思考之後就很好做了。使用max heap維護目前能到達的可用加油站，有「必要」加油時就pop（）一個出來，然後把因為這次加油而能移動到的新加油站們放進max heap。

一開始要先按照dis去做排序，O(nlgn)。
每個加油站最多只會進出max heap一次，O(nlgn)。
主算法過程O(n)。

#include<cstdio>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=10000+5;
struct Fuel
{
    int dis,gas;
    bool operator < (const Fuel& rhs) const {return dis<rhs.dis || (dis==rhs.dis && gas>rhs.gas);}
}fuel[maxn];
int main()
{
    int N,nowgas,tardis;
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&fuel[i].dis,&fuel[i].gas);
    scanf("%d%d",&tardis,&nowgas);
    for(int i=0;i<N;i++) fuel[i].dis=tardis-fuel[i].dis;
    sort(fuel,fuel+N);
    priority_queue<int> pq;
    int p=0,ans=0;
    for(;;)
    {
        while(p<N && nowgas>=fuel[p].dis) pq.push(fuel[p++].gas);
        if(nowgas<tardis)
        {
            if(!pq.size()) {ans=-1;break;}
            nowgas+=pq.top();pq.pop();
            ans++;
        }
        else break;
    }
    printf("%d\n",ans);
}