poj 3250 Bad Hair Day (单调栈)

Bad Hair Day

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 11473		Accepted: 3871

Description

Some of Farmer John's N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows' heads.

Each cow i has a specified height h_i (1 ≤ h_i≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

= =

= - =

= = =

= - = = =

= = = = = = Cows facing right -->
1 2 3 4 5 6

Cow#1 can see the hairstyle of cows #2, 3, 4

Cow#2 can see no cow's hairstyle

Cow#3 can see the hairstyle of cow #4

Cow#4 can see no cow's hairstyle

Cow#5 can see the hairstyle of cow 6

Cow#6 can see no cows at all!

Let c_i denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c₁ through c_N.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input

Line 1: The number of cows, N. Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.

Output

Line 1: A single integer that is the sum of c₁ through c_N.

Sample Input

Sample Output

Source

USACO 2006 November Silver

思路：

暴力N*N肯定会超时，所以就想怎样通过一次遍历就求出结果呢

这里用到单调栈

struct Nod
{
__int64 height;
__int64 startPos;
}node;

定义节点中包含高度height，以及所在的位置

对于输入的数据：10 3 7 4 12 2

初始化栈：先在栈中push进一个节点（inf，-1）以方便后面节点的统一处理，inf为一个无限大的数

i=0时 10<inf 故压入栈 (输入值跟栈顶元素比较)

(inf,-1) (10,0)

i=1时 3<10 压入栈

(inf,-1) (10,0) (3,1)

i=2时 7>3 出栈并计算 sum+=i-H1.startPos-1; 直到 7<10 压栈

(inf,-1) (10,0) (7,2)

i=3时 4<7 压栈

(inf,-1) (10,0) (7,2) (4,3)

i=4时 12>4 出栈并计算 sum+=i-H3.startPos-1;

12>7 出栈并计算 sum+=i-H2.startPos-1;

　　　 12>10 出栈并计算 sum+=i-H0.startPos-1;

12<inf 入栈

(inf,-1) (12,4)

i=5时 2<12 压栈

(inf,-1) (12,4) (2,5)

最后将栈内除了（inf，-1）的其他节点出栈并计算

（2,5）出栈 sum+=i-H5.startPos-1;

（12,4）出栈 sum+=i-H4.startPos-1;

最后得到的sum即为所求。

代码C/C++：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<stack>
 4 
 5 #define INF 1000000001
 6 
 7 using namespace std;
 8 
 9 struct Nod
10 {
11     __int64 height;
12     __int64 startPos;
13 }node;
14 
15 int main()
16 {
17     __int64 n;
18     while(~scanf("%I64d",&n))
19     {
20         __int64 i,a,sum=0;
21         stack <Nod> stk;
22         node.height = INF;
23         node.startPos = -1;
24         stk.push(node);
25         for(i=0;i<n;i++)
26         {
27             scanf("%I64d",&a);
28             while(a>=stk.top().height)
29             {
30                 node = stk.top();
31                 stk.pop();
32                 sum += i - node.startPos - 1;
33             }
34             node.height = a;
35             node.startPos = i;
36             stk.push(node);
37         }
38         while(!stk.empty())
39         {
40             node = stk.top();
41             stk.pop();
42             if(node.height!=INF)    sum += i - node.startPos - 1;
43         }
44         printf("%I64d
",sum);
45     }
46     return 0;
47 }