POJ 3250 Bad Hair Day——————单调栈

本是古典何须时尚 2021-11-05 06:26 204阅读 0赞

# [POJ 3250 Bad Hair Day][] #

Farmer John的奶牛在风中凌乱了它们的发型……  
每只奶牛都有一个身高 h i ( 1 ≤ h i ≤ 1 , 000 , 000 , 000 ) hi(1 ≤ hi ≤ 1,000,000,000) hi(1≤hi≤1,000,000,000)，现在在这里有一排全部面向右方的奶牛，一共有 N N N只 ( 1 ≤ N ≤ 80 , 000 ) (1 ≤ N ≤ 80,000) (1≤N≤80,000)。对于奶牛 i i i来说，如果奶牛 i + 1 ， i + 2 ， … … ， N i+1，i+2，……，N i\+1，i\+2，……，N这些奶牛的身高严格小于奶牛 i i i，则奶牛i可以看到它们凌乱的发型。  
比如下面这个例子：

* * * * = *
    = * * * = *
    = * - * = * 奶牛面向这边-->
    = * = * = *
    = - = = = *
    = = = = = =
    1 2 3 4 5 6

（’\*'表示空的，这是译者为了格式特意弄的，原题没有）

令ci表示第i只奶牛能够看到的发型数量，请计算 c 1 + c 2 + c 3 + … + c N c1 + c2 + c3 + … + cN c1\+c2\+c3\+…\+cN的值  
对于上面这个例子，答案为  3 + 0 + 1 + 0 + 1 + 0 ＝ 5 3 + 0 + 1 + 0 + 1 + 0＝5 3\+0\+1\+0\+1\+0＝5。

--------------------

**单调栈的入门题目**

这个题用单调栈很快，由于每个元素都进栈一次，出栈一次，所以复杂度是 O ( n ) O(n) O(n)的

我们维护一个**单调递减栈**，对于第 i i i个元素，入栈之前有 t t t个元素在栈里，  
如果第 i i i个元素能够入栈，那么就说明在第 i i i头奶牛之前有 k k k头奶牛能够看到它的头顶，所以 a n s + = k ans += k ans\+=k，然后第 i i i个元素入栈  
如果第 i i i个元素不能入栈，那么就得判断栈顶元素与第 i i i个元素的大小，如果栈内有 m m m个元素比第 i i i个元素大，就需要把栈内的 m m m个元素弹出，弹出之后，栈内的元素都比第 i i i个元素大，所以 a n s + = k − m ans += k-m ans\+=k−m，然后让第 i i i个元素入栈

我们通过维护一个单调栈很简单的解决了这个问题

/**
     *　　　　　　　　┏┓　　　┏┓+ +
     *　　　　　　　┏┛┻━━━┛┻┓ + +
     *　　　　　　　┃　　　　　　　┃
     *　　　　　　　┃　　　━　　　┃ ++ + + +
     *　　　　　　 ████━████ ┃+
     *　　　　　　　┃　　　　　　　┃ +
     *　　　　　　　┃　　　┻　　　┃
     *　　　　　　　┃　　　　　　　┃ + +
     *　　　　　　　┗━┓　　　┏━┛
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃ + + + +
     *　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
     *　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃　　+
     *　　　　　　　　　┃　 　　┗━━━┓ + +
     *　　　　　　　　　┃ 　　　　　　　┣┓
     *　　　　　　　　　┃ 　　　　　　　┏┛
     *　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
     *　　　　　　　　　　┃┫┫　┃┫┫
     *　　　　　　　　　　┗┻┛　┗┻┛+ + + +
     */
    /*--------- Hongjie ----------*/
    // #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
    int a[MAXN];
    int st[MAXN];
    
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            int n;
            while(cin>>n) {
        
                    for(int i=0;i<n;++i)
                            cin>>a[i];
                    int t = 0;
                    ll ans = 0;
                    for(int i=0;i<n;++i) {
        
                            while(t>0 && st[t-1]<=a[i])       t--;
                            if(t>0)
                                    ans += t;
                            st[t++] = a[i];
                            // printf("%d%c",t-1,i==n-1?'\n':' ');
                    }
                    cout<<ans<<endl;
            }
    
    
            return 0;
    }

[POJ 3250 Bad Hair Day]: http://poj.org/problem?id=3250