問題
http://community.topcoder.com/stat?c=problem_statement&pm=12025&rd=14737
解き方
貪欲法で、左のアルファベットから決めていけば良い。
決めていく材料として、
あるアルファベットを固定した時に最大のminInvが指定した値以上になり、
かつつくることのできる最も降順の文字列が与えられた文字列よりも大きければ良い。
コード
class StrIIRec {
public: string recovstr(int n, int minInv, string minStr) {
int used[n];
memset(used,0,sizeof(used));
string ret="";
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)if(used[j]==0){
string tmp=ret;
tmp+='a'+j;
for(int k=n-1;k>=0;k--)if(!used[k] && k!=j)tmp+='a'+k;
if(tmp<minStr)continue;
int cost=cnt;
for(int k=0;k<j;k++)if(!used[k])cost++;
used[j]=1;
for(int k=n-1;k>=0;k--)if(!used[k]){
for(int l=k-1;l>=0;l--)if(!used[l])cost++;
}
if(cost<minInv){
used[j]=0;
continue;
}
ret+='a'+j;
for(int k=0;k<j;k++)if(!used[k])cnt++;
break;
}
}
return ret;
}
};
public: string recovstr(int n, int minInv, string minStr) {
int used[n];
memset(used,0,sizeof(used));
string ret="";
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)if(used[j]==0){
string tmp=ret;
tmp+='a'+j;
for(int k=n-1;k>=0;k--)if(!used[k] && k!=j)tmp+='a'+k;
if(tmp<minStr)continue;
int cost=cnt;
for(int k=0;k<j;k++)if(!used[k])cost++;
used[j]=1;
for(int k=n-1;k>=0;k--)if(!used[k]){
for(int l=k-1;l>=0;l--)if(!used[l])cost++;
}
if(cost<minInv){
used[j]=0;
continue;
}
ret+='a'+j;
for(int k=0;k<j;k++)if(!used[k])cnt++;
break;
}
}
return ret;
}
};