萌新集中营第一期——简单数据结构

题解

题目链接：https://vjudge.net/contest/152030

G - Bad Hair Day

题目大意

    农场上有 N (1 ≤ N ≤ 80,000)头牛,都朝右看，每只牛都有一个高度 h (1 ≤ h ≤ 1,000,000,000)，而且它们只能看到比自己矮的，如果被高的挡着就看不见高牛的另一边，求出每只牛看到的牛数的总和
例如以下这个例子:
         =
 =       =
 =   -   =        牛头朝右 -->
 =   =   =
 = - = = =
 = = = = = =
 1 2 3 4 5 6 

Input

包含多组数据，每组包含一个整数 N ，接下来的 N 行是每只牛的高度

Output

输出结果，每个结果占一行

Sample Input

6
10
3
7
4
12
2

Sample Output

5

解题思路

**单调栈**  
    题目是求每只牛能看到的牛数的和，我们可以转化一下思维，题目等同于每只牛能被看到的次数的总和，由于高的牛能挡住矮的牛，所以我们可以利用单调栈或单调队列来处理这个问题，当有一只高牛入栈时，比它矮的牛就会被挡住，也就不会被看到，这就意味着要把比入栈牛矮的牛要弹出栈，能被看到的牛的数量即为栈的大小

代码

#include <stdio.h>
#include <stack>
using namespace std;
int main()
{
    int num;
    long long int cow, ans;
    while(scanf("%d", &num)!=EOF)
    {
        stack <long long int> s;
        ans = 0;
        while(num--)
        {
            scanf("%lld", &cow);
            while(!s.empty()&&cow>=s.top())
            {
                s.pop();
            }
            ans = ans + s.size();
            s.push(cow);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

该题收获

1. 熟悉单调栈
2. 注意细节，输出格式错了使得WA了好几次
3. 学会转换思维
4. 单调栈与单调队列不同的地方在于栈只能在栈顶操作，因此一般在应用单调栈的地方不限定它的大小，否则会造成元素无法进栈