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

· · 题解

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

题目传送门

前言

无聊水篇题解玩玩，类似贪心的思路。

题目大意

有 n 个字符串（保证小写字母），可以将一个字符串中的一个字符改为另一个，记为一次操作。需要找到一个字符串 target，并输出所有字符串都变成 target 的最小次数。

思路

计数排序。定义一个数组（大小为 27，因为有 26 个小写字母）。然后统计一下所有字符串的第 i 个字母（1 \le i \le m）哪个字母出现数量最多。目标单词的第 i 位就选择这个字符。

不理解的同学可以自己拿样例模拟一下 （我相信我的表述足够清除所以懒得写了）。

AC code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+10;
string str[MAXN];
int table[27];
int n,m;

void init(){
    for(int i=1;i<=26;++i)
        table[i]=0;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>str[i];
        str[i]=" "+str[i]; //本人习惯让下标从 1 开始 
    }

    string tar=" "; //同上 
    for(int i=1;i<=m;++i){
        init(); //每次清空 
        for(int j=1;j<=n;++j)
            table[str[j][i]-'a'+1]++;
        char tmp='a';
        for(int j=1;j<=26;++j){
            if(table[tmp-'a'+1]<table[j]){
                tmp=(j-1+'a');
            }
        }
        tar+=tmp;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            ans+=str[i][j]!=tar[j];
        }
    }
    printf("%d",ans);
    return 0;
}

最后祝所有点赞的同学们能够顺利进入省选！学业有成！健健康康！快快乐乐！

The End