input
4
5
hello
10
codeforces
5
eevee
6
appall
output
1
helno
2
codefofced
1
eeeee
0
appall
一次操作：将单个位置上的字母变成任意其他字母
要求给出一个字符串，让你用最少的操作数将字符串转换成每一个字母出现的次数都相同的字符串（不要求字典序，满足条件即可）
例如
\(hello\) \(\rightarrow\) \(helno\) 满足每一个字母都出现一次
\(codeforces\) \(\rightarrow\) \(codefofced\) 满足每一个字母都出现两次
下面开始分析这个题
通过观察可以知道每一个字母出现的次数必须可以被字符串的长度整除，不满足的就排除
if(len%cnt!=0)continue;
开始我们先记录一下每一个字母出现的次数
up(0,n-1)cnt[s[o]-'a']++;
由于我们不知道最后每一个字母会出现多少次，所以我们可以枚举产生最优解
for(int i=(n-1)/26+1;i<=n;i++)
在每一次枚举中，差别值 \(=\) \(\Sigma\) \(\Big|\)应该存在的字母的次数 \(-\) 最后应该保留的次数\(\Big|\)
如果每个字母存在 $ i$ 次，那么最后将会有 $ n / i$ 个字母存在
我们令 \(X\) \(=\) \(n/i\)
因为将不该存在的字母(包括该存在但是次数多的和不该存在的)转变成最后应该存在但不够的字母
一次操作可以减少两个差别值，所以输出的操作数是 差别值/2
如何判断一个字母最后应不应该存在
int cnt[26],tmp[26];
bool cmp(int x,int y){
return tmp[x]<tmp[y];
}
up(0,25){
tmp[o]=i-cnt[o];
id.pb(o);
}
sort(id.begin(),id.end(),cmp);
由此可知排序以后的前 \(X\) 个字母是应该留下的
剩下的字母都是舍弃的
如何计算差异值
up(0,x-1){
res+=abs(cnt[id[o]]-i);
}
up(x,25){
res+=cnt[id[o]];
}
根据上面分析的前 \(X\) 个字母是留下的，他们每个字母的差异值是当前存在的次数减去应该存在的次数的绝对值。
前 \(X\) 以后的字母都是应该舍弃的，因此他们的差异值就是存在过的次数
贪心得到一种最优解
if(res<ans){
ans=res,d=i;
ansid=id;
}
\(res\) 是记录的差异值， \(d\) 是记录的每个字母出现的次数， \(id\) 记录的是那些字母应该出现(因为cmp排序过了)
输出操作数
cout<<ans/2<<endl;
根据上面的分析可知操作数是差异值的一半，输出即可
给每个应该出现的字母标记上应该出现的次数
int used[26]={};
up(0,n/d-1)used[ansid[o]]=d;
把字母出现次数多于d的和不该出现的打成'?'后续进行填字母
up(0,n-1){
if(!used[s[o]-'a']){
s[o]='?';
}
else used[s[o]-'a']--;
}
给？位填上字母
up(0,n-1){
if(s[o]=='?'){
while(j<26&&!used[j])j++;
s[o]=j+'a';
used[j]--;
}
}
输出即可
cout<<s<<endl;
key code
#define fup(o,a,b) for(int o=a;o<=b;o++)
#define up(a,b) for(int o=a;o<=b;o++)
#define mem0(a) memset(a,0,sizeof(a))
const int N=2e5+10;
int n,m,k,a[N],b[N],p[N];
int cnt[26],tmp[26];
bool cmp(int x,int y){
return tmp[x]<tmp[y];
}
void solve(){
//try it again.
cin>>n;
mem0(cnt);
string s;cin>>s;
up(0,n-1)cnt[s[o]-'a']++;
int ans=INF,d=-1;
vector<int>ansid;
for(int i=(n-1)/26+1;i<=n;i++){
if(n%i!=0)continue;
int x=n/i;
vector<int>id;
int res=0;
up(0,25){
tmp[o]=i-cnt[o];
id.pb(o);
}
sort(id.begin(),id.end(),cmp);
up(0,x-1){
res+=abs(cnt[id[o]]-i);
}
up(x,25){
res+=cnt[id[o]];
}
if(res<ans){
ans=res,d=i;
ansid=id;
}
}
cout<<ans/2<<endl;
int used[26]={};
up(0,n/d-1)used[ansid[o]]=d;
up(0,n-1){
if(!used[s[o]-'a']){
s[o]='?';
}
else used[s[o]-'a']--;
}
int j=0;
up(0,n-1){
if(s[o]=='?'){
while(j<26&&!used[j])j++;
s[o]=j+'a';
used[j]--;
}
}
cout<<s<<endl;
}