問題
http://community.topcoder.com/stat?c=problem_statement&pm=8594&rd=11128
解き方
文字を消す回数0〜ｎ回までそれぞれについて、
最も少ない文字を消す回数と頻出する回数すべての場合について全探索する。
O（50*50*50log50=1.25*10^6*log50）で間に合う。
コード
class RoughStrings {
public: int minRoughness(string s, int n) {
int num[26]={};
FORE(i,0,s.size())num[s[i]-'a']++;
vector<int> vx;
FORE(i,0,26)if(num[i]>0)vx.push_back(num[i]);
sort(all(vx));
int ret=1e+9;
for(int sum=0;sum<=n;sum++)for(int right=0;right<=sum;right++){
vector<int> cur=vx;
FORE(j,0,right){
int pos=0;
while(cur[pos]==0)pos++;
cur[pos]--;
}
FORE(j,right,sum){
cur[cur.size()-1]--;
sort(all(cur));
}
int idx=0;
while(cur[idx]==0)idx++;
ret=min(ret,cur[cur.size()-1]-cur[idx]);
}
return ret;
}
};
public: int minRoughness(string s, int n) {
int num[26]={};
FORE(i,0,s.size())num[s[i]-'a']++;
vector<int> vx;
FORE(i,0,26)if(num[i]>0)vx.push_back(num[i]);
sort(all(vx));
int ret=1e+9;
for(int sum=0;sum<=n;sum++)for(int right=0;right<=sum;right++){
vector<int> cur=vx;
FORE(j,0,right){
int pos=0;
while(cur[pos]==0)pos++;
cur[pos]--;
}
FORE(j,right,sum){
cur[cur.size()-1]--;
sort(all(cur));
}
int idx=0;
while(cur[idx]==0)idx++;
ret=min(ret,cur[cur.size()-1]-cur[idx]);
}
return ret;
}
};