#include<istream>
#include<algorithm>
using namespace std;

#include<cstdio>

int max1=0;// no use
int min1=0;// no use

int type_num=0;// 输入种类数 


int array[65];//每种种类对应的面值 

int jie[4];//当前解 
int type[4];//当前解对应的类型 
int num_jie=0;//当前解的数量 
bool is_equal=0;//是否tie 
int cc=0;//记录解的个数，只会为0或者1 

//template<class T>
void swap(int &a, int &b)
{
	int t=a; 
	a=b; 
	b=t;
}

//构造一个解的邮票极其面值 
struct ourdata{
	int data_;
	int type_;
	ourdata(int data=0, int type=-1):data_(data), type_(type){}
	bool operator <(ourdata &other)
	{
		if(data_<other.data_)
		{
			return true;
		}
		else if(data_==other.data_)
		{
			return type_<other.type_?true:false;
		}
		else
		{
			return false;
		}
	}
};


//根据ourdata和num_jie构造一个解 
struct solution{
	struct ourdata data_[4];
	int num_;//解数量 
	int type_;	//解类型数量 
	int max_val_;//解的最大面值 
	solution(){}
	void set(ourdata *data, int num)
	{
		num_=num;
		max_val_=0;
		for(int i=0; i<num; i++)
		{
			data_[i]=data[i];
			if(max_val_<data_[i].data_) max_val_=data_[i].data_;
		}
		
		type_=num;
		for(int x=0; x<num-1; x++)
		{
			for(int y=x+1; y<num; y++)
			if(data_[x].type_==data_[y].type_)
				type_--;
		}
		
		//对解进行排序 
		for(int i=0; i<num-1; i++)
		{
			int tmp=i;
			for(int j=i+1; j<num; j++)
			{
				//if(data_[j].data_<data_[tmp].data_)
				if(data_[j]<data_[tmp])
					tmp=j;
			}
			if(tmp!=i)
			{
				//swap(data_[i], data_[tmp]);
				swap(data_[i].data_, data_[tmp].data_);
				swap(data_[i].type_, data_[tmp].type_);
			}
		}
	}
	
	void display()
	{
		for(int i=0; i<num_; i++)
		{
			printf("%d ", data_[i].data_);
		}
		printf("\n");
		
		for(int i=0; i<num_; i++)
		{
			printf("%d ", data_[i].type_+1);
		}
		printf("\n");
	}

};


solution solution_a, solution_b, temp;


//根据规则比较解，0解质量相同 ，1>， -1<，2同一个解 
int compare_solution(solution &a, solution &b)
{
	if(a.type_>b.type_)
	{
		return 1;
	}
	else if(a.type_<b.type_)
	{
		return -1;
	}
	else
	{
		if(a.num_<b.num_)
		{
			return 1;
		}
		else if(a.num_>b.num_)
		{
			return -1;
		}
		else
		{
			if(a.max_val_>b.max_val_)
			{
				return 1;
			}
			else if(a.max_val_<b.max_val_)
			{
				return -1;
			}
			else
			{
				for(int i=0; i<a.num_; i++)
				{
					if((a.data_)[i].data_==(b.data_)[i].data_&&(a.data_)[i].type_==(b.data_)[i].type_)
					//daozheli
						;
					else
						return 0;
				}
				return 2;
			}
		}
	}
	
}



void process(int val, int k)
{
	if(val==0)
	{
		//记录解 
		ourdata my_data[4];
		for(int i=0; i<num_jie; i++)
		{
			my_data[i].data_=jie[i];
			my_data[i].type_=type[i];
		}
		cc++;
		if(cc==1)
		{
			is_equal=0;
			solution_a.set(my_data, num_jie);
		}
		else if(cc==2)
		{
			temp.set(my_data, num_jie);
			//printf("solution_a:\n");
			//solution_a.display();
			//printf("temp:\n");
			//temp.display();
			int ret=compare_solution(solution_a, temp);

			if(ret==-1)
			{
				is_equal=0;
				solution_a.set(my_data, num_jie);
				//cc--;
			}
			else if(ret==0)
			{
				is_equal=1;
				//solution_b.set(jie, num_jie);
				//solution_b.set_types(type);
				//cc--;
			}

			cc--;
		}
		//printf("is_equal=%d\n", is_equal);
					
		return; 
	}
	else if(val<0)
	{
		return;
	}
	else if(k==4) 
	{
		if(val==0)
		{
			ourdata my_data[4];
			for(int i=0; i<num_jie; i++)
			{
				my_data[i].data_=jie[i];
				my_data[i].type_=type[i];
			}
			cc++;
			if(cc==1)
			{
				is_equal=0;
				solution_a.set(my_data, num_jie);
			}
			else if(cc==2)
			{
				temp.set(my_data, num_jie);
				//printf("solution_a:\n");
				//solution_a.display();
				//printf("temp:\n");
				//temp.display();
				int ret=compare_solution(solution_a, temp);
	
				if(ret==-1)
				{
					is_equal=0;
					solution_a.set(my_data, num_jie);
					//cc--;
				}
				else if(ret==0)
				{
					is_equal=1;
					//solution_b.set(jie, num_jie);
					//solution_b.set_types(type);
					//cc--;
				}
	
				cc--;
			}
			
			//printf("is_equal=%d\n", is_equal);
		}
		
		return; 
	}
	else//回溯法 
	{
		for(int i=0; i<type_num; i++)
		{
			//swap(array[k], array[i]);
			jie[num_jie]=array[i];
			type[num_jie]=i;
			num_jie++;
			process(val-array[i], k+1);
			num_jie--;
			//swap(array[k], array[i]);
		}
	}
} 

int main()
{
	
	while(scanf("%d",&array[type_num])!=EOF)
	{
		max1=array[type_num];
		min1=array[type_num];
		type_num++;
		while(scanf("%d",&array[type_num])!=EOF&&array[type_num]!=0)
		{
			if(max1<array[type_num])
				max1=array[type_num];
			if(min1>array[type_num])
				min1=array[type_num];
			type_num++;
		}
		//type_num--;
		//printf("type_num=%d------------\n",type_num);
		int val;
		while(scanf("%d",&val)!=EOF&&val!=0)
		{
			process(val, 0);
			if(cc==0)
			{
				printf("%d ---- none\n",val);
			}
			else if(cc==1)
			{
				if(is_equal)
				{
					printf("%d (%d): tie\n",val, solution_a.type_);
					/*
					printf("%d (%d): ",val, solution_a.num_);
					for(int x=0; x<solution_a.num_; x++)
						printf("%d ", (solution_a.data_[x].data_));
					printf("\n");
					
					printf("%d (%d): ",val, temp.type_);
					for(int x=0; x<temp.num_; x++)
						printf("%d ", (temp.data_[x].data_));
					printf("\n");
					*/
				}
				else
				{
					printf("%d (%d): ",val, solution_a.type_);
					for(int x=0; x<solution_a.num_; x++)
					{	
						if(x!=solution_a.num_-1)
							printf("%d ", (solution_a.data_[x].data_));
						else
							printf("%d\n", (solution_a.data_[x].data_));
					}
				}
			}
			cc=0;
			is_equal=0;	
			num_jie=0;
		}
		type_num=0;
		max1=0;
		min1=0;
	}
	system("pause");
}

• Re:加了简单注释的 (3390) sicojuy 2011-03-22 20:43:25
  • Re:加了简单注释的 (70) swuroyalty 2011-03-23 08:53:08