题解：P11279 「GFOI Round 2」Abstract String Basic

题意分析

首先，在一个位置放上字母，不相似度为其他地方不是这个字母的个数。

我们可以定义新相似度为其他地方是这个字母的数量，这样的话每一个位置上的不相似度和新相似度加起来正好就是 n-1，所以只要最小化相似度即可。

如果暴力枚举的话。时间一定会超。所以先预处理，将每个字母的数量先统计出来。然后最小化相似度，找一个字母 j，使 cnt_j 最小，需要小心的是如果 j=s_i，应该是 cnt_j-1，可以表示为 cnt[j]-(j==s[i]?1:0)。

代码

#include<bits/stdc++.h>
int cnt[131];
using namespace std;
int main() {
    int n;string s;
    cin>>n>>s;
    for(int i=0;i<n;i++)cnt[s[i]]++;
    for(int i=0;i<n;i++){
        char ans=s[i];
        for(char j='a';j<='z';j+=1){
            if(cnt[j]-(j==s[i]?1:0)<cnt[ans]-(ans==s[i]?1:0)){
                ans=j;
            }
        }
        cout<<ans;
    }
    return 0;
}