CODEVS-1531 山峰

CODEVS-1531 山峰

題目描述 Description

Rocky山脈有n個山峰，一字排開，從西向東依次編號為1, 2, 3, ……, n。每個山峰的高度都是不一樣的。編號為i的山峰高度為hi。

小修從西往東登山。每到一座山峰，她就回頭觀望自己走過的艱辛歷程。在第i座山峰，她記錄下自己回頭能看到的山峰數si。

何謂“能看到”？如果在第i座山峰，存在j

回家之後，小修把所有的si加起來得到S作為她此次旅行快樂值。現在n座山峰的高度都提供給你了，你能計算出小修的快樂值嗎？

輸入描述 Input Description

第一行一個整數n(n<=15000)。

第i+1(1<=i<=n)行是一個整數hi（hi<=10⁹）。

輸出描述 Output Description

僅一行：快樂值。

樣例輸入 Sample Input

5

2

1

3

5

9

樣例輸出 Sample Output

5

數據范圍及提示 Data Size & Hint

說明：s1=0, s2=1, s3=2, s4=1, s5=1。

http://codevs.cn/problem/153

用棧來維護當前點的si值，棧中保存的是一個遞增的序列。

/*
作者:NowAndForever
題目:p1531 山峰
*/
#include
#include
using namespace std;
int main()
{
    int n,i,x,k=0;
    stacks;
    scanf("%d",&n);
    s.push(1000000000); //先壓入一個最大值。好處在於棧永遠不為空，並且每個點的快樂值除了第一個點之外都是1
    for(i=1;i<=n;i++) //每次輸入的值對當前這個點的快樂值沒有影響，當前點的快樂值是棧的所保存的數量。
    {                  //並且棧中需要維護一個遞增的序列，
        k+=s.size()-1;
        scanf("%d",&x); //比如說第一個數為1，第二個數為2，那第一個數就被擋住了，如果第一個數字為2，第2個數字也1，那麼就都壓入棧。
        while(x>s.top()) s.pop();
        s.push(x);
    }
    printf("%d\n",k);
    return 0;
}