算法

POJ2038总结

Team Rankings

题目来源

Description

It’s preseason and the local newspaper wants to publish a preseason ranking of the teams in the local amateur basketball league. The teams are the Ants, the Buckets, the Cats, the Dribblers, and the Elephants. When Scoop McGee, sports editor of the paper, gets the rankings from the selected local experts down at the hardware store, he’s dismayed to find that there doesn’t appear to be total agreement and so he’s wondering what ranking to publish that would most accurately reflect the rankings he got from the experts. He’s found that finding the median ranking from among all possible rankings is one way to go.

The median ranking is computed as follows: Given any two rankings, for instance ACDBE and ABCDE, the distance between the two rankings is defined as the total number of pairs of teams that are given different relative orderings. In our example, the pair B, C is given a different ordering by the two rankings. (The first ranking has C above B while the second ranking has the opposite.) The only other pair that the two rankings disagree on is B, D; thus, the distance between these two rankings is 2. The median ranking of a set of rankings is that ranking whose sum of distances to all the given rankings is minimal. (Note we could have more than one median ranking.) The median ranking may or may not be one of the given rankings.

Suppose there are 4 voters that have given the rankings: ABDCE, BACDE, ABCED and ACBDE. Consider two candidate median rankings ABCDE and CDEAB. The sum of distances from the ranking ABCDE to the four voted rankings is 1 + 1 + 1 + 1 = 4. We’ll call this sum the value of the ranking ABCDE. The value of the ranking CDEAB is 7 + 7 + 7 + 5 = 26.

It turns out that ABCDE is in fact the median ranking with a value of 4.

Input

There will be multiple input sets. Input for each set is a positive integer n on a line by itself, followed by n lines (n no more than 100), each containing a permutation of the letters A, B, C, D and E, left-justified with no spaces. The final input set is followed by a line containing a 0, indicating end of input.

Output

Output for each input set should be one line of the form:

ranking is the median ranking with value value.

Of course ranking should be replaced by the correct ranking and value with the correct value. If there is more than one median ranking, you should output the one which comes first alphabetically.

Sample Input

4
ABDCE
BACDE
ABCED
ACBDE
0

Sample Output

ABCDE is the median ranking with value 4.

我的代码

暴力出所有字母排列很简单,一共也就只有5!种情况而已,关键点在于如何求出每一个排列的值。

我的想法是将每一个字符串都压缩为二进制,压缩的方式根据其映射出的一个矩阵来进行。设ranks[i][j],若ranks[i][j]=1意味着i的排名在j后面。

qq screenshot 20200811195706

例如字符串ABDEC的矩阵如上,其压缩后的状态就是主对角线下方是数字组合。例如这个字符串可以表示为1111101101。可以发现每一位数字都表示两个字母之间的排序先后情况,那么每一个可能的value其实就是和现有的所有字符串压缩后的状态进行异或,求出结果中的1的个数。

状态压缩的过程:

int pretreat(){
	memset(ranks,0,sizeof(ranks));
	int temp=0;
	for (int i=0;i<5;i++){
		for (int j=0;j<5;j++){
			if (rank[j]=='A'+i){
				break;
			}else{
				ranks[i][rank[j]-'A']=1;
			}
		}
	}
	for (int i=0;i<5;i++){
		for (int j=0;j<i;j++){
			temp=temp<<1;
			temp+=ranks[i][j];
		}
	}
	return temp;
}

求异或结果中1的个数:

int solve(int n)
{
	int ans=0;
	while(n)
		ans+=n&1,n>>=1;
	return ans;
}

完整代码:

#include<stdio.h>
#include<string.h>

int n,ans;
int ranks[5][5];
int states[100];//存放字母之间的对应关系,1表示小于 
int flag[10];//字母是否被用过 
char ansarray[10];//存放最终结果 
char rank[10];//字母排列 

//求一个数有多少二进制1 
int solve(int n)
{
	int ans=0;
	while(n)
		ans+=n&1,n>>=1;
	return ans;
}

//将一串字母排列的压缩状态 
int pretreat(){
	memset(ranks,0,sizeof(ranks));
	int temp=0;
	for (int i=0;i<5;i++){
		for (int j=0;j<5;j++){
			if (rank[j]=='A'+i){
				break;
			}else{
				ranks[i][rank[j]-'A']=1;
			}
		}
	}
	for (int i=0;i<5;i++){
		for (int j=0;j<i;j++){
			temp=temp<<1;
			temp+=ranks[i][j];
		}
	}
	return temp;
}

void dfs(int step){
	if (step==5){
		int res;
		int tempsum=0;
		int state=pretreat();
		for (int i=0;i<n;i++){
			//异或 
			res=state^states[i];
			tempsum+=solve(res);
		}
		if (tempsum<ans){
			ans=tempsum;
			rank[5]='\0';
			strcpy(ansarray,rank);
		}
	}else{
		for (int i=0;i<5;i++){
			if (flag[i]==0){
				flag[i]=1;
				rank[step]='A'+i;
				dfs(step+1);
				flag[i]=0;
			}
		}
	}
}

int main()
{
	while(scanf("%d",&n)==1&&n!=0){
		memset(flag,0,sizeof(flag));
		ans=0x3f3f3f3f;
		for (int i=0;i<n;i++){
			scanf(" %s",rank);
			states[i]=pretreat();
		}
		dfs(0);
		printf("%s is the median ranking with value %d.\n",ansarray,ans);
	}
	return 0;
}