Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用stack做的,O(n)算法,why wa?求challenge

Posted by dut200901102 at 2010-12-16 14:29:33 on Problem 2452
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator