[USACO06NOV]Bad Hair Day S(栈)

题目大意:

按顺序给出n头牛的身高,每头牛可以看见它到后出现的牛中第一头身高高过(大于等于)它的牛之间的所有牛,求所有牛总共能看到的牛数

解题思路:

从后往前遍历查看每头牛能看到的牛数,每次进行的比较数量的太多,但我们可以用栈来存储关键信息以减少不必要的比较

代码如下:

#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define N 80005
int a[N];
//每头牛的身高和所能看到的别的牛的头发的数量
struct P {
    int x, num=0;
    P(int x, int num) :x(x), num(num){}
};
stack<P>ans;
ll sum = 0;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,w; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i]; 
	}
    for (int i = n; i; i--) {
        int num = 0;
        while (!ans.empty() && a[i] > ans.top().x) {
            num += ans.top().num+1;
            //去掉冗杂元素
            ans.pop();
        }
        sum += num;
        //存入该头牛的信息
        ans.push(P(a[i],num));
    }
    cout << sum;
}