POJ 2431 Expedition(ツリー)

タイトルリンク:http://poj.org/problem?id=2431
車を運転してL単位距離を走る必要があります.first、あなたの車にはP単位のガソリンがあります.トラックは1単位の道のりごとに1単位のガソリンを消費します.途中にN個のガソリンスタンドがあり、各ガソリンスタンドから終点までの距離A[i]と、各ガソリンスタンドが給油できる容量B[i]を与え、路上で油がないことを保証しながら終点まで最低何回給油する必要があるかを示す.
我々は、「ガソリンスタンドiに到着した時点で、その後いつでもB[i]単位のガソリンを入れることができる権利を得た」と考え、希望する回数をできるだけ少なくしたいので、ガソリンが0になったら、この時点でプラスできるB[i]最大のガソリンスタンドを選ぶべきである.(便宜上、A[i]を各ガソリンスタンドから起点までの距離とし、当然以下の操作を行う前に、ガソリンスタンドを順番に並べます.)
これにより、この問題は優先キューで解決できます.
1.ガソリンスタンドiを通過する際、ネット優先キューにBを入れる.
2.燃料タンクが空になったとき
コードは次のとおりです.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#define MAX_N 10000

using namespace std;
struct aa
{
    int a;
    int b;
};

aa ss[MAX_N+10];
int cmp(aa x,aa y)
{
    return x.a<y.a;
}
int main()
{
    int n,l,p;
    scanf("%d",&n);
    for(int i=n-1;i>=0;i--)
        scanf("%d%d",&ss[i].a,&ss[i].b);
    scanf("%d%d",&l,&p);
    for(int i=0;i<n;i++)
        ss[i].a=l-ss[i].a;
    ss[n].a=l,ss[n].b=0;
	n++;
	sort(ss,ss+n,cmp);
    priority_queue<int> que;
    int ans=0,index=0,tank=p;//ans          ，index       ，tank       
    for(int i=0;i<n;i++)
    {
        int d=ss[i].a-index;
        while(tank-d<0)
        {
            if(que.empty())
            {
                printf("-1
");
                return 0;
            }
            tank+=que.top();
            que.pop();
            ans++;
        }
        tank-=d;
        index=ss[i].a;
        que.push(ss[i].b);
    }
    printf("%d
",ans);
    return 0;
}

参考文献:「プログラム設計コンテストに挑戦する」