【POJ3250】Bad Hair Day

古城微笑少年丶 2022-09-25 10:29 103阅读 0赞

Bad Hair Day

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;17576</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;5926</td> 
  </tr> 
 </tbody> 
</table>

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 *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 *c*1 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 *c* 1 through *cN*.

Sample Input

6
    10
    3
    7
    4
    12
    2

Sample Output

Source

[USACO 2006 November Silver][]

用单调栈求解。

从栈底到栈顶单调递减栈，可以看成每头牛被看到多少次。

#include<cstdio>
    #include<iostream>
    #include<stack>
    #define LL long long
    using namespace std;
    int main() {
    	int n;
    	while(scanf("%d",&n)!=EOF) {
    		stack<int >S;
    		int L;
    		LL ans=0;
    		for(int i=0; i<n; i++) {
    			scanf("%d",&L);
    			while(!S.empty()&&S.top()<=L) {
    				S.pop();
    			}
    			ans+=S.size();
    			S.push(L);
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

[题目地址：http://poj.org/problem?id=3250][http_poj.org_problem_id_3250]

[USACO 2006 November Silver]: http://poj.org/searchproblem?field=source&key=USACO+2006+November+Silver
[http_poj.org_problem_id_3250]: http://poj.org/problem?id=3250