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

这题思路很简单,出栈为n,则栈顶必为小于n并且尚未出栈中最大的,如果出栈数小于栈顶,No。但是我的代码63ms,求大牛降复杂度

Posted by scuwf at 2011-12-09 22:28:35 on Problem 1363
#include<stdio.h>
#include<memory.h>
#define MAX 1001
int hash[MAX];
int main()
{
	int n,c,i,j,top,sign;
	while(scanf("%d",&n),n)
	{
		while(scanf("%d",&c),c)
		{
			sign=0;
			memset(hash,0,sizeof(hash));
			top=c-1;
			hash[c]=1;
			for(i=0;i<n-1;i++)
			{
				scanf("%d",&c);
				if(sign) continue;
				if(c<top)
				{
					sign=1;
					printf("No\n");
				}
				else
				{
					hash[c]=1;
					for(j=c-1;j>=1;j--)
					{
						if(!hash[j])
						{
							top=j;
							break;
						}
					}
				}
			}
			if(!sign) printf("Yes\n");
		}
		printf("\n");
	}
	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