Algoogle

Algorithm for Programming Contest

PKU 2431 Expedition

Category: PKU Tag: greedy

Expedition

問題概要


位置Lに残りの燃料がPのトラックがいて位置0の街に行きたい.
その間にはガソリンスタンドがN個あり, 各ガソリンスタンドではそれぞれ補給できるガソリンの量が決まっている.
なお燃料1につき距離1移動できる.
そのときの最小の給油回数を求めよ.

解法


各ガソリンスタンドに辿り着いたら, そこで補給できる燃料をストックしておく.
各ガソリンスタンドに着くまでに必要な燃料が足りない時, ストックしてある燃料のうち最大のものを補給していく(その回数が答え).
補給できなければ-1

コード


(2431.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <algorithm>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int N, L, P;
pii stand[10010];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        int x, f; scanf("%d%d", &x, &f);
        stand[i] = pii(-x, f);
    }
    stand[N++] = pii(0,0);
    scanf("%d%d", &L, &P);
    sort(stand, stand+N);
    priority_queue<int> fuel;
    int ans = 0;
    for(int i = 0; i < N; i++){
        int x = -stand[i].first;
        int need = L - x;
        while(P < need and !fuel.empty()){
            P += fuel.top(); fuel.pop();
            ans++;
        }
        if(P < need){
            ans = -1;
            break;
        }
        L = x;
        P -= need;
        fuel.push(stand[i].second);
    }
    printf("%d\n", ans);
    return 0;
}

Comments