题意
给你n头牛的高度,每头牛朝向右方,只能看见小于自己高度的牛,当有一头牛的高度大于等于自己时包括这头牛之后的牛也看不见。求所以牛能看见牛数量的总和。
思路
问题可以转化为每头牛被看到的牛的数量的总和,我们可以维护一个单调递增栈,当一个元素x即将入栈时,栈内元素个数就是在左边比他高的牛的数量,且这些牛的高度在位置上从左到右递减,所以我们将n头牛通通入栈,在入栈时栈内元素个数就是对答案的贡献。
AC代码
#include<iostream> using namespace std; const int maxn=8e4+5; typedef long long ll; int s[maxn]; int x,n,tot; ll ans; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>x; while(tot>=1&&s[tot-1]<=x){ tot--; } ans+=tot; //cout<<"*"<<tot<<endl; s[tot]=x; tot++; } cout<<ans; return 0; }