poj2431

poj2431.md

Poj 2431

題目

卡車行駛在長度為 L 公里的道路上，一開始卡車有 P 公升的汽油。 汽油每一公升只能跑一公里，一旦汽油變為 0 ，卡車就會停下。 道路途中有 N 個加油站，分別位於 A[i] 處，加油量為 B[i]。 卡車的油箱大小沒有上限，請問卡車能行駛完道路嗎？ 若不行，請輸出 -1；若可以，請輸出最少的加油次數。 ※ 假設 A[i] 是距起點的距離。

範圍限制

1 <= N <= 10,000
1 <= L <= 1,000,000
1 <= P <= 1,000,000
1 <= A[i] <= L
1 <= B[i] <= 100

分析

考慮 Sample Input 中的第二個測資，卡車只要在 A[1]=20 加 B[1] = 100 的油就足夠了。 我們觀察到一件事：

抵達加油站 i 的位置時，就取得了之後隨時都能補給 B[i] 的權利。

也就是說：

如果車子抵達 A[i] 時還有剩餘的油，那車子可以不用現在就加油，

可以之後油量耗盡時再來加這個加油站的油，或甚至不加。

於是，我我們想得到最少的補給次數，可以利用 Greedy 得出以下方法：

有一個 priority_queue pq

1. 通過 A[i] 時，將 B[i] 加入 pq
2. 當油箱油量耗盡時，
   1. 從 pq 取出最大的數字 B[k] 加至油箱，當作在 A[k] 加過油了。
   2. 當 len(pq) = 0，這代表沒油可加了，輸出 -1

Sample Input

N=4, L=25, P=10
A = [10, 14, 20, 21]
B = [10, 5, 2, 4]
N=3, L=100, P=10
A = [10, 20, 30]
B = [10, 100, 20]

Sample Output

2
1

Code

from heapq import *

def solve(N, L, P):
    # To simplify, add a new gas station to end point.
    pq = []

    A[N] = L
    B[N] = 0

    cnt = 0
    pos = 0
    tank = P

    for i in range(N+1):
        dis = A[i] - pos # distance to the gas station

        # if tank is not enough, add fuel
        while tank < d:
            if len(pq) is 0:
                return -1
            tank += heappop(pq)
            cnt += 1

        # move to the gas station
        pos = A[i]
        tank -= dis
        headpush(pq, B[i])

    return cnt

AC Code

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

struct Stop {
    int pos;
    int fuel;

    bool operator < (const Stop& s) const {
        return pos < s.pos;
    }
};

Stop station[10000+1];

int solve(int N, int L, int P) {
    priority_queue<int> pq;

    station[N].pos = L;
    station[N].fuel = 0;

    int cnt = 0;
    int pos = 0;
    int tank = P;

    for (int i=0; i<=N; i++) {
        int d = station[i].pos - pos;

        while (tank < d) {
            if (pq.empty())
                return -1;
            tank += pq.top();
            pq.pop();
            cnt++;
        }

        pos = station[i].pos;
        tank -= d;
        pq.push(station[i].fuel);
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);

    int N;
    while (cin >> N) {
        for (int i=0; i<N; i++)
        cin >> station[i].pos >> station[i].fuel;

        int L, P;
        cin >> L >> P;

        for (int i=0; i<N; i++)
        station[i].pos = L - station[i].pos;

        sort(station, station + N);

        cout << solve(N, L, P) << "\n";
    }

    return 0;
}