題目大意：

農民約翰的某N頭奶牛正在過亂頭發節！由于每頭牛都意識到自己凌亂不堪的發型，約翰希望統計出能夠看到其他牛的頭發的牛的數量。

每一頭牛i有一個高度所有N頭牛面向東方排成一排，牛N在最前面，而 牛1在最后面.第i頭牛可以看到她前面的那些牛的頭，只要那些牛的高度嚴格小于她的高度，而且 中間沒有比hi高或相等的奶牛阻隔.

讓N表示第i頭牛可以看到發型的牛的數量；請輸出Ci的總和。

思路:

很明顯，這道題是一個單調棧。?
將奶牛一個一個進棧，同時保證棧里面的數字單調遞減（后面必須看得見前面），每次進棧之后求出最后面一頭牛能看見前面的牛的數量，輸出答案即可。?
時間復雜度：O(n)

代碼：

#include <cstdio> #include <iostream> #define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout); using namespace std;long long s[100011],n,a[100011],sum,tail;int main() {fre(badhair);cin>>n;tail=0;a[0]=1e17;for (long long i=1;i<=n;i++)cin>>a[i];for (long long i=1;i<=n;i++){while (a[i]>=s[tail]&&tail) tail--; //模擬棧（可以用queue）tail++; s[tail]=a[i]; //進棧sum=sum+tail-1; //求出答案 }cout<<sum<<"\n";return 0; }

?

---

?

轉載于:https://www.cnblogs.com/hello-tomorrow/p/9323734.html

總結

以上是生活随笔為你收集整理的糟糕的一天【栈】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。