Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用stack做的,O(n)算法,why wa?求challenge#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN=50010; int main() { // freopen("in.txt","r",stdin); int n,a[MAXN],st[MAXN],top; while(scanf("%d",&n)!=EOF) { top=0; for(int i=1;i<=n;++i) { scanf("%d",&a[i]); while(top) { if(a[i]>a[st[top]]) { top--; } else break; } st[++top]=i; } int mn,ans=-1,mnp,now=1; for(int i=1;i<=top;++i) { mn=20000000; mnp=st[i]+1; for(int j=now;j<st[i];++j) { if(a[j]<=mn) { mn=a[j]; mnp=j; } } ans=max(ans,st[i]-mnp); now=st[i]+1; } printf("%d\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator