Sample Output
TAAGATAC 7 ACGTACGTAA 6 AAGTTACCAA 12
题意：给定n个DNA，求一个目标串，使得每个序列变换成目标所需次数最少。
思路：贪心。每一位选存在最多的变化即可。
代码:
#include#include const int N = 1005; const int M = 55; int t, n, m, vis[500], ans; char g[M][N]; void init() { ans = 0; scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++) scanf("%s", g[i]); } char cal(int i) { char c; int Max = 0; memset(vis, 0, sizeof(vis)); for (int j = 0; j < n; j ++) { vis[g[j][i]] ++; if (Max < vis[g[j][i]]) { Max = vis[g[j][i]]; c = g[j][i]; } else if (Max == vis[g[j][i]] && g[j][i] < c) { c = g[j][i]; } } ans += (n - vis[c]); return c; } void solve() { for (int i = 0; i < m; i ++) printf("%c", cal(i)); printf("\n%d\n", ans); } int main() { scanf("%d", &t); while (t--) { init(); solve(); } return 0; }