Codeforces 58 D. Calendar

問題

n個の都市の名前がある。
これらを一行に二つずつ、文字dで区切って並べる。
各行は全て同じ文字数でなくてはならない。（このような並べ方が存在することは保証されている）

並べた後のn/2行の文字列を、そのまま順につなげた文字列が辞書順で最小になるように求めよ。

制約条件

n≦10^4

方針

一行の文字列の長さをlen+1とすると、
i文字の都市とlen-i文字の都市がペアになる。
どういうペアが辞書順最小かというと、辞書順最小の二つをつないだもの。

辞書順最小の二つをどちらを先にもってくるかは、2通り試してみればよい。

ソースコード

int n;
char d;
map<int,vs> M;
void run(){
  cin>>n;
  rep(i,n){
    string in; cin>>in;
    M[in.size()].pb(in);
  }
  cin>>d;
  int mn=(int)1e9,mx=0;
  fr(i,M){
    sort(all(i->second));
    mn=min(mn,i->first);
    mx=max(mx,i->first);
  }
  vs ans;
  fr(i,M){
    if(i->first*2>mn+mx)break;
    if(i->first*2==mn+mx){
      rep(j,i->second.size()/2){
        string s=min(i->second[j*2]+d+i->second[j*2+1],i->second[j*2+1]+d+i->second[j*2]);
        ans.pb(s);
      }
    }
    else{
      int r=mx+mn-i->first;
      rep(j,i->second.size()){
        string s=min(i->second[j]+d+M[r][j],M[r][j]+d+i->second[j]);
        ans.pb(s);
      }
    }
  }
  sort(all(ans));
  rep(i,ans.size())cout<<ans[i]<<endl;
}