SDUT 3661 MoutainTop(单调栈)解题报告

2016-08-30 1,369 次浏览 解题报告

题面

MoutainTop
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
金石山脉有n个山峰,一字排开,从西向东依次编号为1, 2, 3, ……, n。编号为i的山峰高度为hi。每个山峰的高度两两不同
小木示从西向东依次爬过这n个山峰,到每一个山峰的山顶的时候,他都会往西边眺望,并且会记录下自己能看到的山峰的个数。
(比如说小木示现在在4号山峰,前四号山峰的高度分别为9,4,5,1。他现在能看到的山峰个数就是2,因为第二个山峰被第三个山峰挡住了)
严格的来说,小木示在i位置的时候,对于一个山峰j (j < i),如果不存在一个山峰k满足hj < hk (j < k < i)。则山峰j是可见的。
小木示把自己记录的山峰的个数加和作为这次爬山的快乐值,现在给你n个山峰的高度,求小木示的快乐值。

Input
多组输入,首先输入一个n(1<=n<=10^6),表示山峰的个数。 接下来一行n个数,表示对应山峰的山峰的高度(1<=h<=10^6)。

Output
输出小木示的快乐值

Example Input
4
1 6 5 1

Example Output
4

Author
JueChen

所需基础

单调栈

解题思路

这道题是小木示出的题,学过单调栈的同学不难看出是一道裸题(我当时怎么就没看出来啊 QAQ)。解题思路其实很容易理解,我们维护一个栈来记录当前可见的山,读入山高数据之后,把栈中所有比当前山高小的元素全部弹出(道理不难理解,一旦出现了高山,那么下一次计算数量的时候,比此山矮的山必然会被挡住,也就不会被计算到,因此可以把它们安全弹出),然后再将当前山高入栈。由于本轮读入的山高只会影响到下一次计数,因此我们可以在每轮输入前进行计数累加。
另外,关于单调栈,再推荐一道类似题目: POJ 3250 Bad Hair Day

参考代码

#include <cstdio>
#include <stack>
using namespace std;

int main(int argc, char const *argv[]) {
    int n, data;
    while(~ scanf("%d", &n)) {
        scanf("%d", &data);
        stack<int> s;
        s.push(data);
        long long sum = 0;
        while(--n) {
            sum += s.size();
            scanf("%d", &data);
            // 弹出比当前山高小的山
            while(!s.empty() && s.top()<data) {
                s.pop();
            }
            s.push(data);
        }
        printf("%lld\n", sum);
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/08/30/sdut-3661.dream

还不快抢沙发

添加新评论