SRM 563 DIV1 Easy - FoxAndHandle (復習××)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12331&rd=15185
文字列が与えられて、その文字をシャッフルして元の文字にランダムに挿入する。
挿入後の文字列が与えられた時、元の文字列のうち辞書順に最小のものを求める。
解き方
文字の種類については、与えられた各文字を２で割ったものになる。
次に文字の順番については、ひとつ選ぶとその前の文字は選べなくなる。
選ぶべき文字の種類を満たし、かつ辞書順になるよう小さいアルファベットから
上の判定を繰り返していく。
コード
class FoxAndHandle {
public: string lexSmallestName(string S) {
int num[26]={0};
string ans="";
FORE(i,0,S.size())num[S[i]-'a']++;
FORE(i,0,26)num[i]=num[i]/2;
while(accumulate(num,num+26,0)>0){
pair<char,int> best=make_pair('z'+1,-1);
FORE(i,0,S.size()){
if(num[S[i]-'a']==0)continue;
int count[26]={},invalid=0;
FORE(j,i,S.size())count[S[j]-'a']++;
FORE(j,0,26)if(num[j]>count[j])invalid=1;
if(invalid)continue;
best=min(best,make_pair(S[i],i));
}
ans+=best.first;
num[best.first-'a']--;
S=S.substr(best.second+1);
}
return ans;
}
};
public: string lexSmallestName(string S) {
int num[26]={0};
string ans="";
FORE(i,0,S.size())num[S[i]-'a']++;
FORE(i,0,26)num[i]=num[i]/2;
while(accumulate(num,num+26,0)>0){
pair<char,int> best=make_pair('z'+1,-1);
FORE(i,0,S.size()){
if(num[S[i]-'a']==0)continue;
int count[26]={},invalid=0;
FORE(j,i,S.size())count[S[j]-'a']++;
FORE(j,0,26)if(num[j]>count[j])invalid=1;
if(invalid)continue;
best=min(best,make_pair(S[i],i));
}
ans+=best.first;
num[best.first-'a']--;
S=S.substr(best.second+1);
}
return ans;
}
};
