4851374_wa.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int x[105];
int y[105];
int num[7];
int quan[7];
int dif[7][7];
int main()
{
	int i,j,best,pair,left,last,temp,all;
	while(cin>>n>>k)
	{
		best=999999999;
		memset(num,0,sizeof(num));
		if(n==0&&k==0) return 0;
		for(i=0;i<n;i++)
		{
			cin>>temp;
			x[i]=temp;
			num[temp]++;
		}
		for(i=0;i<k;i++)
		{
			quan[i]=i+1;
		}
		do
		{
			j=0;
			all=0;
			for(i=0;i<k;i++)
			{
				int count;
				for(count=0;count<num[quan[i]];count++)
				{
					y[j]=quan[i];
					j++;
				}
			}
			memset(dif,0,sizeof(dif));
			for(i=0;i<n;i++)
			{
				if(x[i]!=y[i]) 
				{
					all++;
					dif[x[i]][y[i]]++;
				}
			}
			//ganghao jiaohuan
			pair=0;
			for(i=1;i<=k;i++)
			{
				for(j=i+1;j<=k;j++)
				{
					if(dif[i][j]&&dif[j][i])
					{
						int sm=dif[i][j]<dif[j][i]?dif[i][j]:dif[j][i];
						pair+=sm;
					}
				}
			}
			left=all-pair*2;
			if(left==0) last=pair;
			else last=left-1+pair;
			if(last<best) best=last;
		}while(next_permutation(quan,quan+k));
		cout<<best<<endl;
	}
	return 0;
}