Uva 1368 DNA Consensus String, ACM/ICPC Seoul 2006 算法竞赛入门

    输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离之和最小。
两个等长的DNA序列的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（第1个和第4个）。
    输入整数m和n（4≤m≤50，4≤m≤1000），以及m个长度为n的DNA序列（只包含字母A,G,C,T），
输出到m个序列的Hamming距离最小和的DNA序列和对应的距离，如果有多解，输出字典序最小的那个。

#include <stdio.h>
#include <string.h>
const char X[] = {'A', 'C', 'G', 'T'};
int main()
{
    int m, n, t, i, j, d, ct[4];
    char dna[50][1005];
    char ans[1005];
    scanf("%d", &t);
    while(t--)
    {
        d = 0;
        scanf("%d%d", &m, &n);
        i = 0;
        while(i < m)
            scanf("%s", dna[i++]);
        //统计每列各种字符数
        for(j = 0; j < n; ++j)
        {
            memset(ct, 0, sizeof(ct));
            for(i = 0; i < m; ++i)
            {
                if('A' == dna[i][j]) ++ct[0];
                else if('C' == dna[i][j]) ++ct[1];
                else if('G' == dna[i][j]) ++ct[2];
                else ++ct[3];
            }
            //找出每列出现最多的字符
            int max = -1;
            char ch = 255;
            for(i = 0; i < 4; ++i)
            {
                if(ct[i] > max)
                {
                    max = ct[i];
                    ch = X[i];
                }
                else if(ct[i] == max)
                    if(X[i] < ch)
                        ch = X[i];
            }
            //计算距离
            for(i = 0; i < m; ++i)
                if(dna[i][j] != ch) ++d;
            ans[j] = ch;
        }
        ans[n] = '\0';
        printf("%s\n%d\n", ans, d);
    }
    return 0;
}