题目大意:
按顺序给出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;
}