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;
}