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

· · 题解

思路

看到这道题，我的第一反应是搜索，但是搜索的代码交上去后，迎接我的是：爆零。于是我意识到搜索是行不通的，我便开始想其他办法，我在苦思冥想一会儿之后，想出了一个好办法：既然题目要求用最少的字符数将这些单词都改成一样的，那何不枚举这些单词的每一位，然后将所有单词的每一位都替换成当前这一位出现频率最高的字母呢？想出这个方法之后就好办了，我们可以建立一个变量 ans 存储答案，然后枚举这 N 个单词的每一位，然后每一次循环都建立一个 map 数组 a，然后建立变量 maxx 用来存储当前位出现频率最高的字母的出现次数，在外层循环内再套一层内层循环，内层循环用来统计当前位出现频率最高的字母的出现次数，统计完毕后再将 ans 加上 N-maxx 的结果就行了，最后输出 ans 即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
string s[101];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>s[i];//输入
    for(int j=0;j<m;j++){//枚举每一位
        int maxx=0;
        map<char,int>a;
        for(int i=1;i<=n;i++){//统计最大值
            a[s[i][j]]++;
            maxx=max(maxx,a[s[i][j]]);
        }
        ans+=n-maxx;
    }
    cout<<ans<<endl;//输出
    return 0;
}

AC 记录。