UVa 12674 - Go up the ultras

contents

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

Problem

一個山峰高度 h[i] 如果算是突起,則必須符合

  • 到其他更高的山峰之間有經過低於 h[i] - 150000 的可能
  • 如果本身就是最高峰,則高度至少要 150000

Sample Input

1
2
3
4
5
0 10000 100000 884813 0
7
0 100000 0 200000 180000 200000 0

Sample Output

1
2
4
4 6

Solution

維護一個遞增的單調堆,而第二個元素存放掃描時經過的最低點。然後從左往右掃一次、再從右往左掃一次,分別得到每一個點往左、往右找到最高峰的情況。

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;
int n;
int h[1048576], a[1048576];
int main() {
while(scanf("%d", &n) == 1) {
for (int i = 0; i < n; i++)
scanf("%d", &h[i]), a[i] = h[i];
stack< pair<int, int> > stk;
for (int i = 0; i < n; i++) {
if (!stk.empty()) {
stk.top().second = min(stk.top().second, h[i]);
}
while (!stk.empty() && stk.top().first <= h[i]) {
pair<int, int> p = stk.top();
stk.pop();
if (!stk.empty())
stk.top().second = min(stk.top().second, p.second);
}
if (!stk.empty()) {
a[i] = min(a[i], h[i] - stk.top().second);
}
stk.push(make_pair(h[i], h[i]));
}
while (!stk.empty())
stk.pop();
for (int i = n - 1; i >= 0; i--) {
if (!stk.empty()) {
stk.top().second = min(stk.top().second, h[i]);
}
while (!stk.empty() && stk.top().first <= h[i]) {
pair<int, int> p = stk.top();
stk.pop();
if (!stk.empty())
stk.top().second = min(stk.top().second, p.second);
}
if (!stk.empty()) {
a[i] = min(a[i], h[i] - stk.top().second);
}
stk.push(make_pair(h[i], h[i]));
}
int f = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= 150000) {
if (f++) printf(" ");
printf("%d", i + 1);
}
}
puts("");
}
return 0;
}
/*
5
0 10000 100000 884813 0
7
0 100000 0 200000 180000 200000 0
*/