【UVA – 1368】DNA Consensus String【紫书】

【UVA – 1368】DNA Consensus String【紫书】

问题链接:https://vjudge.net/problem/UVA-1368

udebug链接:https://www.udebug.com/UVa/1368

Solution:

解决方法很简单,开一个二维数组,然后依次位置记一下数,找到出现次数最多的那个字符就好。关于要求的数字,对每个位置用m减去那个位置上出现最多字符的出现次数,再进行求和就是答案。

关键需要注意的一点是,如果存在多个距离最小的串,要输出字典序最小的那个,下面的代码中通过根据四种字符字典序大小来设定判断顺序,以此来实现字典序最小。

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1010;
int data[LIM][4];
char str[LIM];

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(data, 0, sizeof data);
        int m, n;
        scanf("%d%d", &m, &n);
        for (int i = 0; i < m; i++) {
            scanf("%s", str);
            for (int j = 0; str[j]; j++) {
                if (str[j] == 'A') data[j][0]++;
                else if (str[j] == 'C') data[j][1]++;
                else if (str[j] == 'G') data[j][2]++;
                else if (str[j] == 'T') data[j][3]++;
            }
        }
        int maxi, state, ans = 0;
        for (int i = 0; i < n; i++) {
            maxi = 0;
            for (int j = 0; j < 4; j++) {
                if (data[i][j] > maxi) {
                    maxi = data[i][j];
                    state = j;
                }
            }
            if (state == 0) putchar('A');
            else if (state == 1) putchar('C');
            else if (state == 2) putchar('G');
            else if (state == 3) putchar('T');
            ans += m - maxi;
        }
        putchar('\n');
        printf("%d\n", ans);
    }
    return 0;
}