DNA序列 UVa1368

原题链接：https://cn.vjudge.net/problem/UVA-1368

大概题意：

输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1, 4个字符不同）。

输入整数m和n（4≤m≤50, 4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

 

分析：我的思路是从0-n-1同时遍历所有字符串，然后每一个访问，我们对字符进行计数，然后看一下哪个字符出现的次数是最多的。像上面的例子，我们从0号位置开始，0号位置，从上往下有：T T A T T，我们就记录T-4次，A-1次，然后发现T出现的次数是最多的，所以最优解的第0号位置就是T。

然后我们怎么算总距离呢？也是上面的例子，我们在每一次遍历的时候，先全部加起来，然后再减去我们选择的最优解。比如0号位置，T-4，A-1，我们就先加5，然后减去4，得到1。相当于所有字符串在这个位置（0号位），为这个距离，贡献了1.

接下来是AC代码：

#include<iostream>
#include<cstring>
#include<map>
#include<vector>
using namespace std;

map<char,int> cnt;

int main()
{
//	freopen("in.txt","r",stdin);
	int T;
	cin>>T;
	while(T--)
	{
		int m,n;
		cin>>m>>n;
		string s[m];//保存每一次测试用例的所有字符串 
		for(int i=0; i<m; i++)
		{
			cin>>s[i];
		}
		int allsum=0;//最后要输出的 “距离 ” 
		vector<char> ans;//最后要输出的最优解 
		for(int j=0; j<n; j++)
		{
			//对于每一列，先存到计数器里面 
			cnt.clear();
			for(int i=0; i<m; i++)
			{
				cnt[s[i][j]]++;
			}
			//再找一下计数器里面谁最大 
			map<char,int>::iterator i=cnt.begin();
			char c=i->first;
			int sum=i->second;
			for(i=cnt.begin(); i!=cnt.end(); i++)
			{
				allsum+=i->second;
				if(i->second>sum)
				{
					sum=i->second;
					c=i->first;
				}
			}
			allsum-=sum;
			ans.push_back(c);
		}
		
		//输出 
		for(int i=0; i<ans.size(); i++)
		{
			cout<<ans[i];//输出字符串 
		}
		cout<<endl;
		cout<<allsum<<endl;
	}
	return 0;
}

这里我用map来表示字符和计数器之间的映射，如果不会map，可以用一个数组，比如a[0]表示‘A’出现的次数，a[1]表示‘C’出现的次数，然后要注意字典序顺序，这里map可以很好的解决字典序问题是因为map会自动排序。然后从begin（），遍历到最后一个元素就好了。

Over.