#include<iostream.h>
#include<fstream.h>
bool flags[64];//木棍使用标记
int sticks[64];//每段木棍的长度

int mini;      //木棍最短的可能
int object;
int number;
int remainlength;
bool getIt;
void remove(int length,bool remainf[],int sub[]);
void recover(int length,bool remainflags[],int sub[]);
void find(int length,int position,int target,int remain[],int sub[],bool remainflags[],int n);
void main()
{
//	fstream cin("c:\\1.txt",ios::in);
	int remain[64];//剩下的木棍
	int sub[64];
	bool remainflags[64];
	int n;
	int sum;
	int t=0;
	while(cin>>n)
	{
		remainlength=n;
		if(!n)break;
		sum=0;
		for(int i = 0; i < n; i++)
		{
			cin>>sticks[i];
			sum+=sticks[i];
		}
		
		for(i=0;i<n-1;i++)//选择排序
		{
			int lable=i;
			for(int j=i+1;j<n;j++)
				if(sticks[lable]<sticks[j]) lable=j;
			if(i!=lable)
			{
				sticks[i]^=sticks[lable]^=sticks[i]^=sticks[lable];
			}
		}
		
		for(i=0;i<n;i++)
		cout<<sticks[i]<<' ';
	cout<<endl;

		mini=sticks[0]-1;
		
		getIt=false;
		while((mini<sum) && (!getIt))
		{
			mini++;
			for(i=0;i<64;i++)flags[i]=true;
			while(sum%mini!=0)mini++;
			number=sum/mini;
			getIt=false;
			int length=0;
			for(int l=0;l<n;l++)
			{
				if(flags[l])
				{
					remain[length]=sticks[l];
					sub[length]=l;
					remainflags[length++]=true;//未使用
				}
			}
			int target=mini-remain[0];
			object=target;
			remainflags[0]=false;
			if(target)find(length,1,target,remain,sub,remainflags,1);
				else
				{
					flags[0]=false;
					int count=1;
					bool hoho=true;
					for(int m=1;m<n;m++)
					{						
						if(sticks[m-1]==sticks[m])
						{
							flags[m]=false;
							count++;
						}
						else break;
					}
					if(count==n)break;
					int length=0;
					for(int l=0;l<n;l++)
					{
						if(flags[l])
						{
							remain[length]=sticks[l];
							sub[length]=l;
							remainflags[length++]=true;//未使用
						}
					}
					int target=mini-remain[0];
					object=target;
					remainflags[0]=false;
					if(target)find(length,1,target,remain,sub,remainflags,count+1);
				}
			
		}
		t++;
		cout<<"第"<<t<<"组测试数据结果：";
		cout<<mini<<endl;
	}
}

void find(int length,int position,int target,int remain[],int sub[],bool remainflags[],int n)
{
	if(position>=length || getIt)return;
	if(remain[position]<target)
	{
		target-=remain[position];
		remainflags[position]=false;
		find(length,position+1,target,remain,sub,remainflags,n);
		int lable1=position+1;
		while(lable1<length&& remain[lable1]==remain[position])lable1++;
		target+=remain[position];
		remainflags[position]=true;
		find(length,lable1,target,remain,sub,remainflags,n);
	}
	else if(target<=remain[position] && target>=remain[length-1])
	{
		int left=position-1;
		int right=length;
		int mid;
		while((left+1)!=right)
		{
			mid=(left+right)/2;
			if(remain[mid]>target)left=mid;
			else if(remain[mid]<target)right=mid;
			else
			{
				remainflags[mid]=false;
				cout<<"第"<<n<<" of "<<number<<"根木棍："<<endl;
				n++;
				if((n-number)==1)
				{
					remove(length,remainflags,sub);
					getIt=true;
					break;
				}
				remove(length,remainflags,sub);
				int remain1[64];
				int sub1[64];
				bool remainflags1[64];
				int length1=0;
				for(int l=0;l<remainlength;l++)
				{
					if(flags[l])
					{
						remain1[length1]=sticks[l];
						sub1[length1]=l;
						remainflags1[length1++]=true;//未使用
					}
				}
				int target1=mini-remain1[0];
				remainflags1[0]=false;
				if(target1)find(length1,1,target1,remain1,sub1,remainflags1,n);
					else
					{
						n++;
						if((n-number)==1)
						{
							getIt=true;
							break;
						}
					}
				recover(length,remainflags,sub);
				remainflags[mid]=true;
				n--;
				break;
			}
		}
		position=mid;
		find(length,position+1,target,remain,sub,remainflags,n);
		int lable1=position+1;
		while(lable1<length&& remain[lable1]==remain[position])lable1++;
//		target+=remain[position];
//		remainflags[position]=true;
		find(length,lable1,target,remain,sub,remainflags,n);
	}
	else//比最小的还要小，没有希望了
	{
		return;
	}

}

void remove(int length,bool remainflags[],int sub[])
{
	int first=0;
	for(int i=0;i<length;i++)
	if(!remainflags[i])
	{
		if(first++)cout<<'+';
		flags[sub[i]]=false;
		cout<<sticks[sub[i]];
		
	}
	cout<<'='<<mini<<endl;
}

void recover(int length,bool remainflags[],int sub[])
{
//	int first;
	for(int i=0;i<length;i++)
	if(!remainflags[i])
	{
//		if(first++)cout<<'+';
		flags[sub[i]]=false;
//		cout<<sticks[sub[i]];
	}
//	cout<<'='<<mini<<endl;
}

• 我提交了15次了。。。现在TLE…… (1808) wangchao 2007-04-21 15:53:31
• 我提交了15次了。。。现在TLE…… (1808) wangchao 2007-04-21 15:53:32
  • Re:我提交了15次了。。。现在TLE…… (63) winboycool 2007-04-21 16:28:32