PKU 2038 Team Rankings
http://poj.org/problem?id=2038
n個のABCDEを並べ替えた文字列が与えられる。
このとき、ABCDEを並べ替えた文字列で、順番のずれがもっとも小さいもののうち、辞書順最小のものを出力しろというような問題。
順列を生成して、コスト計算して最小を出力
int n; string in[1000]; int ranking[128]; void solve(){ rep(i,n) cin >> in[i]; pair<int,string> ans(10000,""); string a="ABCDE"; do{ int co=0; rep(i,5) ranking[a[i]] = i; rep(i,n) rep(j,5)rep(k,j) co += ranking[in[i][j]]<ranking[in[i][k]]; ans=min(ans,mp(co,a)); }while(next_permutation(ALL(a))); printf("%s is the median ranking with value %d.\n",ans.S.c_str(),ans.F); } main(){ while(cin >> n, n) solve(); }