POJ-3250-Bad Hair Day

题目描述：

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:

1
2
3
4
5
6
7
=
=       =
=   -   =         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.

输入：

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.

输出：

Line 1: A single integer that is the sum of c1 through cN.

输入示例：

1
2
3
4
5
6
7
6
10
3
7
4
12
2

输出示例：

1
5

题目大意：

有一排奶牛，每个奶牛可以看到它右边身高严格比它小的奶牛发型，问这一排奶牛可以看到的奶牛发型总数。

思路：

这道题是单调栈模板题。

具体做法就是在当前奶牛的右边找一个大于等于（原题说要严格小于，所以等于也算边界）它身高的奶牛的位置（由于求大于等于，所以维持一个单调递减栈），然后两者位置之差再减一就是中间的奶牛数量，每一个奶牛都做此操作即可求得结果。当然有一种情况是它找不到右边身高大于等于它的奶牛。这时可以把最后一个奶牛有一个无限高的奶牛，然后用该位置去减栈中每个奶牛的位置（n+1-x-1 = n-x）。

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
 * @Date: 2019-09-04 16:39:06
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-06 21:41:17
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>

using namespace std;
struct node{
    int a,x;
    node(){}
    node(int _a, int _x):x(_x),a(_a){}
};

stack<node> s;

int main(){
    //freopen("in.txt","r",stdin);
    int n;
    long long ans = 0;
    scanf("%d",&n);
    node temp;
    for(int i = 1; i <= n; i++){
        scanf("%d",&temp.a);
        temp.x = i;
        //单调递减栈
        //找到了第一个比当前栈顶大的值（刚读入的值）。
        while(s.size() && s.top().a <= temp.a){
            //计算坐标差
            ans += i-s.top().x-1;
            s.pop();
        }
        s.push(temp);
    }
    //当前栈顶元素的右边没有比他更高的元素了，用最右边的无限高减去该元素位置。
    while(s.size()){
        ans += n-s.top().x;
        s.pop();
    }
    printf("%lld\\n",ans);
    return 0;
}