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遍了,还是WA,实在想不出其他什么测试数据了, 大家帮忙跑些测试数据吧,谢谢啦

Posted by clinton at 2008-06-02 17:58:49 on Problem 1010
#include <iostream>
#define MAX 1000
using namespace std;

int s_num = 0;
int c_num = 0;
int stamp[MAX];
int cus[MAX];

int res[MAX][5];
int res_num = 0;
int temp[2][5];

void sort1(int array[], int num);
void sort2(int array[MAX][5], int num);
void getAnswer(int array[MAX][5], int num, int dst);
void tryy(int start, int time, int i, int dst);
int getLen(int array[5]);
int getHigh(int array[5]);

int main()
{
	int a;
	while(cin>>a)
	{
		s_num = 0;
		c_num = 0;
		if(a !=0)
		{
			stamp[s_num++] = a;
			while(cin>>a)
			{
				if(a == 0) break;
				else
				{
					stamp[s_num++] = a;
				}
			}
			while(cin>>a)
			{
				if(a == 0) break;
				else
				{
					cus[c_num++] = a;
				}
			}
			//cout<<"dst:"<<s_num<<endl;
			//第一轮输入结束,开始处理
			//对邮票排序
			sort1(stamp, s_num);
			//cout<<"fd"<<endl;
			for(int trav = 0; trav < c_num; trav++)
			{
				int time = 1;
				int ii = 0;
				int dst = cus[trav];
				int start = 0;
				res_num = 0;
				for(int i1 = 0; i1 < MAX; i1++)
					for(int j1 = 0; j1 < 5; j1++)
						res[i1][j1] = 0;
				for(int i2 = 0; i2 < 2; i2++)
					for(int j2 = 0; j2 < 5; j2++)
						temp[i2][j2] = 0;
				tryy(start, time, ii, dst);
				//对结果按邮票种类数排序
				sort2(res, res_num);
				/*for(i = 0; i < res_num; i++)
				{	
					for(int j = 0; j <= 4; j++)
					cout<<res[i][j]<<" ";
					cout<<endl;
				}*/
				getAnswer(res, res_num, dst);
			}
		}
		else
		{
			while(cin>>a)
			{
				if(a == 0) break;
				else
				{
					cus[c_num++] = a;
				}
			}
			for(int i3 = 0; i3 < c_num; i3++)
			{
				cout<<cus[i3]<<" ---- none"<<endl;
			}
		}
		
	}
	return 0;
}

void tryy(int start, int time, int now, int dst)
{
	for(int ii = start; ii < s_num; ii++)
	{
		//条件入口
		if(time <=4 && (stamp[ii] + now) <= dst)
		{
			temp[0][time] = stamp[ii];
			temp[1][time] = ii;
			//匹配成功
			int to = stamp[ii] + now;
			
			if(to == dst)
			{	
                bool tag[5] = {false, false, false, false, false};
				for(int k1 = 1; k1 <= time; k1++)
				{
					res[res_num][k1] = temp[0][k1];
					//cout<<"temp:"<<temp[0][k]<<" ";
				}
				//算度数
				for(int k2 = 1; k2 <= time; k2++)
				{ 
					if(tag[k2] == false)
					{
						res[res_num][0] ++;
						for(int kk = k2; kk <= time; kk++)
						{
							if(temp[1][kk] == temp[1][k2])
							{
								tag[kk] = true;
							} 
						}
					}
				}
				res_num ++;

			}//////////
			
			else
			{
				tryy(ii ,time + 1, now + stamp[ii], dst);
			}
			//for(int n1 = 0; n1 <= 1; n1++)
			//	for(int n2 = 0; n2 <= 4; n2++)
				//	temp[][n2] = 0;

		}
	}
}
//插入排序1
void sort1(int array[], int num)
{
	for(int pos = 1; pos <= num -1; pos++)
	{
		int j = pos - 1;
		int temp = array[pos];
		while(j >= 0 && array[j] > temp)
		{
			array[j + 1] = array[j];
			j -- ;
		}
		array[j + 1] = temp;
	}
}

//插入排序2
void sort2(int array[MAX][5], int num)
{
	for(int pos = 1; pos <= num -1; pos++)
	{
		int j = pos - 1;
		int temp1 = array[pos][0];
		int temp2 = array[pos][1];
		int temp3 = array[pos][2];
		int temp4 = array[pos][3];
		int temp5 = array[pos][4];
		while(j >= 0 && array[j][0] < temp1)
		{
			array[j + 1][0] = array[j][0];
			array[j + 1][1] = array[j][1];
			array[j + 1][2] = array[j][2];
			array[j + 1][3] = array[j][3];
			array[j + 1][4] = array[j][4];
			j -- ;
		}
		array[j + 1][0] = temp1;
		array[j + 1][1] = temp2;
		array[j + 1][2] = temp3;
		array[j + 1][3] = temp4;
		array[j + 1][4] = temp5;
	}
}
//
void getAnswer(int array[MAX][5], int num, int dst)
{
	if(num == 0)
	{
		cout<<dst<<" ---- none"<<endl;
		return ;
	}
	//round1 得到牌数最少的
	int res1[MAX + 1];
	int res2[MAX + 1];
	int best = array[0][0];
	int least = 10;
	int largest = 0;
	for(int i1 = 0; i1 < num; i1++)
	{
		if(array[i1][0] == best)
		{
			int len = getLen((array[i1]));
			
			if(len < least)
			{
				least = len;
				res1[0] =0;
				res1[0] ++;
				res1[res1[0]] = i1;	
			}
			else if(len == least)
			{
				res1[0] ++;
				res1[res1[0]] = i1;
			}
		}
	}
	//cout<<"FF:"<<res1[0]<<endl;
	//得到最大的
	for(int i2 = 1; i2 <= res1[0]; i2++)
	{
		int high = getHigh((array[res1[i2]]));
		//cout<<"high:"<<high<<endl;
		if(high > largest)
		{
			res2[0] =1;
			res2[res2[0]] = res1[i2];	
			largest = high;
		}
		else if(high == largest)
		{
			res2[0] ++;
			res2[res2[0]] = i2;
		}
	}
	if(res2[0] > 1)
	{
		cout<<dst<<" ("<<array[0][0]<<"): tie"<<endl;
	}
	else if(res2[0] == 1)
	{
		int pos = res2[1];
		//cout<<"pos:"<<pos<<endl;
		int len = getLen(array[pos]);
		cout<<dst<<" ("<<array[0][0]<<"):";
		for(int k = 1; k <= len; k++)
		{
			cout<<" "<<array[pos][k];
		}
		cout<<endl;
	}
	return ;
}
int getLen(int array[5])
{
	int num = 0;
	for(int i = 1; i<= 4; i++)
	{
		if(array[i] != 0)
			num ++;
	}
	return num;
}
int getHigh(int array[5])
{
	int max = 0;
	for(int i = 1; i<= 4; i++)
	{
		if(array[i] > max)
			max = array[i];
	}
	return max;
}



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