优先队列 POJ 2431 Expedition

题意：一辆卡车要行驶L长度，初始有P油，每行驶一个单位长度消耗一单位油。有n个加油站可以加油，问最少加油几次才能行驶L长度，如果不能输出-1

分析：按照挑战书的解法，每走到一个加油站相当于获得一次加油的权利，等到油没有的时候再选择之前可加油的站的最大油量加上，可以用优先队列高效得到最大值，如果队列里没油使得继续前进则为-1

收获：换一种思考方式，加上高效的数据结构能完美解决难题

代码：

/************************************************

* Author        :Running_Time

* Created Time  :2015/9/14 星期一 08:28:25

* File Name     :POJ_2431.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e4 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

struct Oil  {

    int p, v;

    bool operator < (const Oil &r) const {

        return p < r.p;

    }

}o[N];

int main(void)    {

    int n;

    while (scanf ("%d", &n) == 1)   {

        int L, P;

        for (int i=n; i>=1; --i)    scanf ("%d%d", &o[i].p, &o[i].v);

        scanf ("%d%d", &L, &P);

        for (int i=n; i>=1; --i)    o[i].p = L - o[i].p;        //起点到加油站的距离

        o[++n].p = L; o[n].v = 0;

        sort (o+1, o+1+n);

        priority_queue<int> Q;

        int ans = 0, pos = 0;

        for (int i=1; i<=n; ++i)    {

            int d = o[i].p - pos;

            P -= d;

            while (P < 0)   {

                if (Q.empty ()) {

                    ans = -1;   break;

                }

                P += Q.top ();  Q.pop ();

                ans++;

            }

            if (ans == -1)  break;

            pos = o[i].p;

            Q.push (o[i].v);

        }

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

    }

    return 0;

}

巴特西

优先队列 POJ 2431 Expedition

最新文章

热门文章