Sticks Problem POJ - 2452

本文主要是介绍Sticks Problem POJ - 2452，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2452

单调栈找出每个数a[i]右边第一个小于等于他的数在哪 记为pos[i] 然后在[i,pos[i]-1]内找一个最靠左的最大值在哪 记为p 则[i,p]即为所求

#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;stack <int> stk;
int maxx[200010],id[200010];
int ary[50010],pos[50010];
int n;void init()
{int i;while(!stk.empty()) stk.pop();for(i=n;i>=1;i--){while(!stk.empty()&&ary[i]<ary[stk.top()]) stk.pop();if(stk.empty()) pos[i]=n+1;else pos[i]=stk.top();stk.push(i);}
}void pushup(int cur)
{if(maxx[2*cur]>=maxx[2*cur+1]){maxx[cur]=maxx[2*cur];id[cur]=id[2*cur];}else{maxx[cur]=maxx[2*cur+1];id[cur]=id[2*cur+1];}
}void build(int l,int r,int cur)
{int m;if(l==r){maxx[cur]=ary[l];id[cur]=l;return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}void query(int pl,int pr,int &res1,int &res2,int l,int r,int cur)
{int m;if(pl<=l&&r<=pr){if(res1<maxx[cur]){res1=maxx[cur];res2=id[cur];}return;}m=(l+r)/2;if(pl<=m) query(pl,pr,res1,res2,l,m,2*cur);if(pr>m) query(pl,pr,res1,res2,m+1,r,2*cur+1);
}int main()
{int i,ans,res1,res2;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++) scanf("%d",&ary[i]);init();build(1,n,1);ans=-1;for(i=1;i<=n;i++){if(i<pos[i]-1){res1=0,res2=0;query(i,pos[i]-1,res1,res2,1,n,1);ans=max(ans,res2-i);}}printf("%d\n",ans);}return 0;
}

 

这篇关于Sticks Problem POJ - 2452的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---