C. Equal Frequencies地址链接把cnt数组清空统计原串中字母的数量cinns;fill(cnt,cnt26,0);for(inti0;is.size();i)cnt[s[i]-a];把每种字母数量从大到小排序structNode{intid,cnt;}v[26];boolcmp(Node a,Node b){returna.cntb.cnt;}for(inti0;i26;i)v[i]{i,cnt[i]};sort(v,v26,cmp);统计一下保留种类数为多少时需要做出的更改最少可以枚举一下种类数intans0x3f3f3f3f3f3f3f3fll,ansid0;for(intused1;used26;used){if(n%used!0)continue;intmn/used;intnow0;for(inti0;iused;i)nowabs(v[i].cnt-m);for(intiused;i26;i)nowv[i].cnt-0;now/2;ansmin(ans,now);if(ansnow)ansidused;}coutansendl;更新调整后每种字母的个数for(inti0;iansid;i){cnt[v[i].id]n/ansid;}for(intiansid;i26;i){cnt[v[i].id]0;}先确定字符串的哪些位置需要修改再求出修改后的字符串for(inti0;is.size();i){boolvis0;for(inti0;iused;i){if(s[i]-av[i].id)vistrue;}if(!vis)s[i] ;elseif(cnt[s[i]-a])cnt[s[i]-a]--;elses[i] ;}for(inti0;is.size();i){if(s[i]! )continue;intvis-1;for(intj0;jansid;j){if(cnt[v[j].id]){visv[j].id;break;}}s[i]visa;cnt[vis]--;}coutansendl;完整代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;intn;string s;intcnt[26];structNode{intid,cnt;}v[26];boolcmp(Node a,Node b){returna.cntb.cnt;}voidsolve(){cinns;fill(cnt,cnt26,0);for(inti0;is.length();i)cnt[s[i]-a];intans0x3f3f3f3f3f3f3f3fll,ansid0;for(inti0;i26;i)v[i]{i,cnt[i]};sort(v,v26,cmp);for(intused1;used26;used){if(n%used!0)continue;intmn/used;intnow0;for(inti0;iused;i)nowabs(v[i].cnt-m);for(intiused;i26;i)nowv[i].cnt;now/2;ansmin(ans,now);if(ansnow){ansidused;}}coutansendl;for(inti0;iansid;i)cnt[v[i].id]n/ansid;for(intiansid;i26;i)cnt[v[i].id]0;for(inti0;is.length();i){boolvisfalse;for(intj0;jansid;j){if(v[j].ids[i]-a){vistrue;break;}}if(!vis)s[i] ;elseif(cnt[s[i]-a])--cnt[s[i]-a];elses[i] ;}for(inti0;is.length();i){if(s[i]! )continue;intvis-1;for(intj0;jansid;j)if(cnt[v[j].id]){visv[j].id;break;}s[i]visa;--cnt[vis];}coutsendl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}
