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

TianX · 2026-03-05 12:35:22 · 题解

P15606 题解

思路

不难想到只需要将每个位置上的字母改成这个位置上出现频率最高的字母就可以了。设 i 位置上的出现频率最高的字母出现次数为 cnt_i，那么最终答案就是所有 n-cnt_i 的和。

:::success[code]{open}

#include<bits/stdc++.h>
using namespace std;
#define int long long
string s[105];
int n,m,ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=0;i<m;i++){
        vector<int>t(26,0);
        for(int j=1;j<=n;j++) t[s[j][i]-'a']++;//统计次数 
        int ma=-1e9;
        for(int j=0;j<26;j++) ma=max(ma,t[j]);//找频率最高的 
        ans+=n-ma;//累加答案 
    }cout<<ans;
    return 0;
}

:::