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

· · 题解

题目大意

这道题简单的说就是需要使用最少的次数使得所有单词变成一样的。

解题思路

对于每个位置 j（0 \le j < m），我们要选一个字母，让这个位置上的字母全部变成它。

这里一定是选择出现次数最多的字符，因为这样我们需要修改的字符串就越少。因此我们假设这个位置出现最多的字母的次数为 x，则这个位置需要修改的次数为 n - x。

把每个位置要改的次数加起来，就是答案。

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
string s[110];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int j=0;j<m;j++)
    {
        int t[30]={0},x=0;
        for(int i=1;i<=n;i++) 
        {
            t[s[i][j]-'a'+1]++;
            x=max(x,t[s[i][j]-'a'+1]);
        }
        ans+=n-x;
    }
    cout<<ans;
    return 0;
}

最后祝大家开学快乐。