| ||||||||||
| 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