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

_ego_ · 2026-03-05 17:39:00 · 题解

思路

题目要求把 N 个长度为 M 的字符串变成完全一样，每次改一个字符，问最少改几次。

最终所有字符串相同，意味着每个位置上的字符在所有字符串中都是一样的。所以对于每个位置 j，我们要选一个字符，让所有字符串的这个位置都变成它。

每个位置独立，总修改次数就是每个位置上的修改次数相加。对于位置 j，统计 26 个字母的出现次数，选出现最多的那个作为目标，这一位需要改 N-\max(cnt) 次。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,ans=1e9,cnt[26];
string s[105];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> s[i];

    for(int col=1;col<=m;col++){
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;i++) cnt[s[i][col-1]-'a']++;

        int mx=0;
        for(int i=0;i<26;i++) if(cnt[i]>mx) mx=cnt[i];

        int now=n-mx;
        for(int j=1;j<=m;j++){
            if(j==col) continue;
            memset(cnt,0,sizeof cnt);
            for(int i=1;i<=n;i++) cnt[s[i][j-1]-'a']++;
            mx=0;
            for(int i=0;i<26;i++) if(cnt[i]>mx) mx=cnt[i];
            now+=n-mx;
        }
        ans=min(ans,now);
    }
    cout << ans;

    return 0;
}