字符串：zoj 2207 || poj 2038 Team Rankings

【转】http://blog.csdn.net/zxy_snow/article/details/6131852

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
typedef struct NODE{
	char str[10];
	int pos[5];
}NODE;
NODE arr[121];//存枚举出来的字符串 
NODE brr[101];//存输入的字符串 
int visit[5];
int cou,d;
char temp[5];
void DFS()  //深搜，枚举出来120种情况。。。 
{
	int i;
	if( d == 5 )
	{
		strcpy(arr[cou].str,temp);
		cou++;
		return ;
	}
	for(i=0; i<5; i++)
		if( !visit[i] )
		{
			temp[d] = i + 'A';
			visit[i] = 1;
			d++;
			DFS();
			d--;
			visit[i] = 0;
		}
	}
void init()
{
	memset(visit,0,sizeof(visit));
	cou = d = 0;
}
char str[110][7];
int main()
{
	int n,i,k,sum,j,p,tmp,max,tempi;
	init(); 
	DFS();
	while( scanf("%d",&n)!=EOF && n )
	{
		sum = 0;
		for(i=0; i<n; i++)
			scanf("%s",brr[i].str);
			
		for(i=0; i<cou; i++) 		//存每个字符的位置 
		{
			for(k=0; k<5; k++)
				arr[i].pos[arr[i].str[k]-'A'] = k;
		}
		for(i=0; i<n; i++)			//同上 
		{
			for(k=0; k<5; k++)
				brr[i].pos[brr[i].str[k]-'A'] = k;
		}
		
		max = INT_MAX,tempi;
		for(i=0; i<cou; i++)
		{
			sum = 0;
			for(k=0; k<n; k++)
			{
				tmp = 0;
				for(j=0; j<5; j++)// 比较两个字符的相对位置是否一样。一样的话差值相乘肯定大于0的。 
					for(p=j+1; p<5; p++)
						if( ( arr[i].pos[j] - arr[i].pos[p] ) * 
										( brr[k].pos[j]-brr[k].pos[p] ) < 0 )
							tmp++;
				sum += tmp;
			}
			if( sum < max )//保存最小的value以及标号 
			{
				max = sum;
				tempi = i;
			}
		}
		
		printf("%s is the median ranking with value %d./n",arr[tempi].str,max);
	}
return 0;
}