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

Re:我的一直循环下去了

Posted by AlbertLiu at 2008-09-11 20:25:10 on Problem 1011
In Reply To:对没AC的同学一点提示 Posted by:PlayerZ at 2008-08-07 08:58:43
我的程序对其他数据都是瞬间出结果,但你这个就好像死循环了,不过也找不到错误啊?
还有,好像很多通过了的程序也很慢才能出结果或者也死了。

#include <stdio.h>
#include <iostream>
using namespace std;
int a[65],stack[65],used[65],poped;
int main()
{  
//	freopen("in.txt","r",stdin);

	int i,j,k,n,max,sum,temp,div,stacklen;
	while( scanf("%d",&n) && n )
	{
		sum=max=0;
		for(i=0;i<n;++i)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			if(max<a[i])
				max=a[i];	// 输入木棍的最大值。
		}
		for(i=0;i<n-1;)		// 冒泡排序,从大到小排列木棍。
		{
			k=n;
			for(j=n-1; j>i; --j)
				if(a[j]>a[j-1])
				{
					temp=a[j];
					a[j]=a[j-1];
					a[j-1]=temp;
					k=j;
				}
			i=k;
		}
		
//		for(i=0;i<n;++i)	cout<<a[i]<<"  ";
//		cout<<endl;
		
		i=max;			// 从木棍最大长度开始搜索。
//		cout<<"max= "<<max<<"  sum="<<sum<<endl;
		//		long xx=1;
		while(1)		// 搜索。
		{
			while(sum%i)	++i;	// 结果长度 肯定能整除总长度
//			cout<<"\n ******  i= "<<i<<"  n="<<n<<endl;
			if(i==sum)	break;
			memset(stack,0,sizeof(stack));
			memset(used,0,sizeof(used));
			stack[1]=0;	stacklen=1; used[0]=1;
			div=a[stack[stacklen]];			// div: 当前搜索的一段木棍的总长度。
			j=0;	poped=-1;
			int flag=0;
			while(stacklen>0 && stacklen<n)
			{		
				++j;

		//		++xx;
		//		if(xx==500)
		//			break;
	//			cout<<"stacklen="<<stacklen<<"   j="<<j<<endl;
	//			int xy=0;
	//			for(k=1;k<=stacklen;++k)
	//			{	printf("stack[%d]= %d\t",k,a[stack[k]]);	xy+=a[stack[k]];	}	
	//			cout<<"\ni="<<i<<"  sum="<<sum<<"   all stack="<<xy<<"\t";
	//			cout<<endl<<"div="<<div<<"   poped="<<poped<<endl;

				while( div<i && j<n)
				{
					if(used[j]==0 && div+a[j]<=i && a[j]!=poped)
					{
						div+=a[j];
						used[j]=1;
						++stacklen;
						stack[stacklen]=j;
					}
					++j;
	//				cout<<"######  div="<<div<<endl;
				}
				poped=-1;
				if(div==i)
				{
					j=1;
					while(used[j]==1)	++j;
					div=0;	--j;
				}
				else
				{
					j=stack[stacklen];
					poped=a[j];
					--stacklen;
					used[j]=0;

					if(div-a[j]<0)
						div=i;
					div-=a[j];
					if(div==0 && j>n/5)		// 这个判断就是专们为你的数据设计的,
					{						// 有他能过你的数据,但其他数据可能过不了了。
						flag=j-1;
						while(used[flag]==1 && flag>0) --flag;
						if(flag==0)
							break;		
					}
				}
			}
//			cout<<endl;
			if(stacklen==n)
				break;
			++i;
		}
		cout<<i<<endl;
	}
	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