【算法初级篇】优先队列+贪心

例题：POJ2431(xepedition)
题意：一辆卡车要行驶L单位距离。最开始时，卡车上有P单位汽油，每向前行驶1单位距离消耗1单位汽油。如果在途中车上的汽油耗尽，卡车就无法继续前行，即无法 到达终点。途中共有N个加油站，加油站提供的油量有限，卡车的油箱无限大，无论加多少油都没问题。给出每个加油站距离终点的距离和能够提供的油量，问卡车 从起点到终点至少要加几次油？如果不能到达终点，输出-1。

思路：在经过加油站i时，往优先队列里加入Bi；当燃料空是，如果队列空，则无法到达终点（return -1），否则取出优先队列中的最大元素，并用来给卡车加油！

代码：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define MAX_N 10000

int len = 0;
int p_oil = 0;
int n_station = 0;
int A[MAX_N + 1] = {0};
int B[MAX_N + 1] = {0};

void solve()
{
    A[n_station] = len;
    B[n_station] = 0;
    n_station++;

    priority_queue<int> que;                //优先队列，这里还不懂，值越大越优先么在这里？

    int ans = 0;
    int position = 0;
    int tank = p_oil;
    int next_d = 0;

    for (int i = 0; i < n_station; i++)
    {
        next_d = A[i] - position;

        while (tank - next_d < 0)        //have not enough oil to next target
        {
            if (que.empty())
            {
                puts("-1");
                return;
            }

            tank += que.top();
            que.pop();
            ans++;                        //add one to ans;
        }

        tank -=next_d;
        position = A[i];
        que.push(B[i]);
    }

    printf("have to add %d times!\n", ans);
}

int main(void)
{
    printf("how many gas station?\n");
    scanf("%d", &n_station);
    printf("how long distance?\n");
    scanf("%d", &len);
    printf("how many oil now?\n");
    scanf("%d", &p_oil);

    printf("请输入每个车站的距离!\n");
    for (int i = 0; i < n_station; i++)
    {
        scanf("%d", &A[i]);
    }

    printf("请输入每个车站能提供!\n");
    for (int j = 0; j < n_station; j++)
    {
        scanf("%d", &B[j]);
    }

    solve();

    return 0;
}

运行结果：