当前位置：首页 > news >正文

cf ratring1600 7月29日

news 2026/8/2 8:49:49

C. Equal Frequencies

地址链接
把cnt数组清空，统计原串中字母的数量

cin>>n>>s;fill(cnt,cnt+26,0);for(inti=0;i<s.size();i++)++cnt[s[i]-'a'];

把每种字母数量从大到小排序

structNode{intid,cnt;}v[26];boolcmp(Node a,Node b){returna.cnt>b.cnt;}for(inti=0;i<26;i++)v[i]={i,cnt[i]};sort(v,v+26,cmp);

统计一下保留种类数为多少时
需要做出的更改最少
可以枚举一下种类数

intans=0x3f3f3f3f3f3f3f3fll,ansid=0;for(intused=1;used<=26;used++){if(n%used!=0)continue;intm=n/used;intnow=0;for(inti=0;i<used;i++)now+=abs(v[i].cnt-m);for(inti=used;i<26;i++)now+=v[i].cnt-0;now/=2;ans=min(ans,now);if(ans==now)ansid=used;}cout<<ans<<endl;

更新调整后每种字母的个数

for(inti=0;i<ansid;i++){cnt[v[i].id]=n/ansid;}for(inti=ansid;i<26;i++){cnt[v[i].id]=0;}

先确定字符串的哪些位置需要修改
再求出修改后的字符串

for(inti=0;i<s.size();i++){boolvis=0;for(inti=0;i<used;i++){if(s[i]-'a'==v[i].id)vis=true;}if(!vis)s[i]=' ';elseif(cnt[s[i]-'a'])cnt[s[i]-'a']--;elses[i]=' ';}for(inti=0;i<s.size();i++){if(s[i]!=' ')continue;intvis=-1;for(intj=0;j<ansid;j++){if(cnt[v[j].id]){vis=v[j].id;break;}}s[i]=vis+'a';cnt[vis]--;}cout<<ans<<endl;

完整代码：

#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;intn;string s;intcnt[26];structNode{intid,cnt;}v[26];boolcmp(Node a,Node b){returna.cnt>b.cnt;}voidsolve(){cin>>n>>s;fill(cnt,cnt+26,0);for(inti=0;i<s.length();i++)++cnt[s[i]-'a'];intans=0x3f3f3f3f3f3f3f3fll,ansid=0;for(inti=0;i<26;i++)v[i]={i,cnt[i]};sort(v,v+26,cmp);for(intused=1;used<=26;used++){if(n%used!=0)continue;intm=n/used;intnow=0;for(inti=0;i<used;i++)now+=abs(v[i].cnt-m);for(inti=used;i<26;i++)now+=v[i].cnt;now/=2;ans=min(ans,now);if(ans==now){ansid=used;}}cout<<ans<<endl;for(inti=0;i<ansid;i++)cnt[v[i].id]=n/ansid;for(inti=ansid;i<26;i++)cnt[v[i].id]=0;for(inti=0;i<s.length();i++){boolvis=false;for(intj=0;j<ansid;j++){if(v[j].id==s[i]-'a'){vis=true;break;}}if(!vis)s[i]=' ';elseif(cnt[s[i]-'a'])--cnt[s[i]-'a'];elses[i]=' ';}for(inti=0;i<s.length();i++){if(s[i]!=' ')continue;intvis=-1;for(intj=0;j<ansid;j++)if(cnt[v[j].id]){vis=v[j].id;break;}s[i]=vis+'a';--cnt[vis];}cout<<s<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}