题解 P2866 【[USACO06NOV]Bad Hair Day S】

Cripple_Abyss · 2020-06-11 19:05:56 · 题解

题目传送门

本题考查对栈的应用

题目解法：

1. 每次输入一头牛的身高，找比这头牛矮的，出栈

2. 剩下的牛皆可以看到这只牛

3. ans值加等于栈中牛的个数

4. 这头牛入栈

Code：

#include<bits/stdc++.h>
using namespace std;
int n,t;
long long ans; //注意要开long long 
stack <int> a;
int main() {
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>t;
        while (!a.empty()&&a.top()<=t)  
            a.pop();
        ans+=a.size();
        a.push(t);
    }
    cout<<ans;
    return 0;
}

都看到这了，点个赞呗QwQ