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

gjr2025 · 2026-03-05 09:26:53 · 题解

题目要求

一次操作可以将单词中的一个字符改为另一个字符，问要多少次操作能让所有旗帜上的单词相同。

思路

如果将所有单词改为 s 所需修改的总字符数最少， 则 s 的第 i 个字母就是所有字符串中第 i 个位置出现次数最多的字母。求出 s 再和每个字符串比较即可。

Code

#include<bits/stdc++.h>
using namespace std;
string a[105];
int v[205];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }   
    int sum = 0;
    for(int i=0;i<m;++i){
        memset(v,0,sizeof v);
        for(int j=1;j<=n;++j){//统计每个字母出现次数 
            v[(int)a[j][i]]++;
        }
        int ans = 0,ansi = 0;
        for(int j=1;j<=200;++j){//找出哪个字母出现次数最多 
            if(v[j] > ans){
                ans = v[j];
                ansi = j;
            }
        }
        char c = ansi;
        for(int j=1;j<=n;++j){//和每个字符串作比较 
            if(a[j][i] != ansi) sum++;
        }
    }
    cout<<sum;
    return 0;
}