POJ - 3250 - Bad Hair Day【单调栈】题解

青旅半醒 2021-07-25 02:38 323阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

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 hi (1 ≤ hi ≤ 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 ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.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 c1 through cN.  
**Sample Input**  
6  
10  
3  
7  
4  
12  
2  
**Sample Output**  
5

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<stack>
    using namespace std;
    int main()
    { 
    	stack<int>st;
    	long long n,ans=0;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{ 
    		int h;
    		cin>>h;
    		while(!st.empty()&&h>=st.top())///该头牛可以被左边多少头牛看见 
    		  st.pop(); ///栈中递减序列 
    		ans+=st.size();
    		st.push(h);
    	}
    	cout<<ans<<endl;
    	return 0;
    }