题解：P15606 [ICPC 2021 Jakarta R] Uniform Maker

· · 题解

卡了一会，但很快想出来了qwq。

思路

我们以样例一为例，可以发现：

所有单词第一位分别为 \texttt{c，p，b，i，b，r}，所以选出现次数最多的 \texttt{b}，那么总共需要修改第一位 4 次。

同理，所有单词第二位分别为 \texttt{a，a，o，c，a，o}，所以选出现次数最多的 \texttt{a}，那么总共需要修改第二位 3 次。

以此类推，最后会改成 \texttt{balm}，总共修改 14 次。

这样就显而易见了，选择该位出现次数最多的字符。设该位出现次数最多的字符的数量为 k，此时修改次数为 n - k，累加所有修改次数即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
string s[105];
int ans = 0;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> s[i];        
    }
    for(int i = 0; i < m; i++){
        vector<int> lt(30, 0);
        for(int j = 1; j <= n; j++){
            lt[int(s[j][i] - 'a' + 1)]++;
        }
        int maxcx = 0;
        for(int j = 1; j <= 26; j++){
            maxcx = max(maxcx, lt[j]);
        }
        ans += n - maxcx;
    }
    cout << ans << '\n';
}