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

5
0 10000 100000 884813 0
7
0 100000 0 200000 180000 200000 0

Sample Output

4
4 6

Solution

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

#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
 */