解題區/解題區 - UVa

UVa 13014 - Keep it energized

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 $N$ 道關卡，每一道關卡需要消耗能量 $E_i$ 才能通過，每一個關卡有能量商店，只能進行一次交易，一旦交易成功，不管先前的剩餘能量為何，直接消耗 $C_j$ 元補能量到 $S_j$，請問至少花費多少錢才能闖完所有關卡。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 4
1 2 3 4 5
1 6 5
2 14 10
5 5 4
3 7 5
3 4
14 11 2015
1 14 23
2 11 9
3 1987 1
1 2039 33

Sample Output

1
2
14
-1

Solution

明顯地，維護一個最小堆，每一個元素紀錄 <在哪一關買商店, 累計多少花費, 購買時有多少能量>，隨著掃描線移動，依序出隊那些無法抵達的元素，並且隊首花費就是到這一關的最少花費 $C$，再依序嘗試在新的商店購買能量，累計花費後入隊。

時間複雜度 $\mathcal{O}(N \log M)$

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <time.h>
using namespace std;
const int MAXN = 131072;
int E[MAXN];
long long sumE[MAXN];
vector< pair<int, int> > shop[MAXN];
struct ELE {
    long long cost;
    int x, e;
    ELE(long long cost = 0, int x = 0, int e = 0):
    cost(cost), x(x), e(e) {}
    bool operator<(const ELE &v) const {
        if (cost != v.cost)
            return cost < v.cost;
        if (x != v.x)
            return x < v.x;
        return e < v.e;
    }
};
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &E[i]), shop[i].clear();
        for (int i = 0; i < M; i++) {
            int L, S, C;
            scanf("%d %d %d", &L, &S, &C);
            shop[L].push_back(make_pair(S, C));
        }
        
        for (int i = 1; i <= N; i++)
            sumE[i] = sumE[i-1] + E[i];
        
        set<ELE> S;
        for (int i = 1; i <= N; i++) {
            while (!S.empty()) {
                ELE u = *S.begin();
                if (u.e < sumE[i-1] - sumE[u.x-1])
                    S.erase(S.begin());
                else
                    break;
            }
            if (S.empty() && i != 1) {
            } else {
                long long mm = i == 1 ? 0 : S.begin()->cost;
                for (int j = 0; j < shop[i].size(); j++) {
                    pair<int, int> p = shop[i][j];
                    if (p.first >= E[i])
                        S.insert(ELE(mm + p.second, i, p.first));
                }
            }
        }
        while (!S.empty()) {
            ELE u = *S.begin();
            if (u.e < sumE[N] - sumE[u.x-1])
                S.erase(S.begin());
            else
                break;
        }
        if (S.empty())
            puts("-1");
        else
            printf("%lld\n", S.begin()->cost);
    }
    return 0;
}