題目鏈接：點擊查看

題目大意：給出n只牛，高度參差不齊，所有的牛都朝向右邊，他們可以看到右邊所有沒有遮擋并且比自己低的牛，問每只牛可以看到的牛的數量總和是多少

題目分析：這個題目讓求每只牛看到的牛的數量，我們可以轉換一下，轉化成每只牛被看到過多少次，這樣就可以轉換成單調隊列/單調棧的題目了，大概就是維護一下當前位置x之前有多少頭牛比自己高即可，很簡單的實現，直接看代碼吧

代碼：

單調棧：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF){stack<int>st;LL ans=0;while(n--){int num;scanf("%d",&num);while(st.size()&&st.top()<=num)st.pop();ans+=st.size();st.push(num);}printf("%lld\n",ans);}return 0; }

單調隊列：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;while(scanf("%d",&n)!=EOF){deque<int>q;LL ans=0;while(n--){int num;scanf("%d",&num);while(q.size()&&q.back()<=num)q.pop_back();ans+=q.size();q.push_back(num);}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3250 Bad Hair Day(单调队列/单调栈)的全部內容，希望文章能夠幫你解決所遇到的問題。

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