洛谷P2866 [USACO06NOV] Bad Hair Day S

P2866 [USACO06NOV] Bad Hair Day S

可以分析出：只要找到每一个数的右边第一个大于此数的位置即可
而“每头奶牛能看到多少头牛”
<->“每头牛能被多少牛看到”
于是 我们维护一个一维的栈

stack<int> s;

每次读入一头奶牛的身高(x)
比这头牛矮的全部出栈

while(!s.empty() and s.top()<=x) s.pop();

栈剩下的牛都可以看到这头奶牛,因此仅需

ans+=s.size();

ACcode

#include<bits/stdc++.h>
using namespace std;
const int N=8e4+5;
int n;
long long ans=0; //这里注意ans要long long型
stack<int>s;
int main(){cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;while(!s.empty() and s.top()<=x) s.pop();ans+=s.size();s.push(x);}cout<<ans<<endl;return 0;
}
//Author:AAA_jiancaipifa