A - Bad Hair Day 单调栈

题意

  给你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;
}

 

 

  

上一篇:/bin/bash^M: bad interpreter: No such file or directory


下一篇:278. First Bad Version