SRM381 Div2 1000

問題

いくつかの整数numbersが与えられる。そこから正確にn個の整数を用いて、それを連結させてできる最大の整数を返す。ただし、何度も同じ整数を使うことができるが、必ずすべての整数を1度以上使わなければならない。

考え方

できるだけ大きい数字を作るので、与えられる整数のうち一番大きいものをできるだけ使った方がよいことがわかる。なので、n-numbers.size()個はnumbersで一番大きいものになる。
それを並び替えて一番大きな数字を作るが、各整数を文字列に直した場合、「2つの隣り合う文字列a,bについて、a+b>b+aとなる」ように並び替えればよい。(バブルソート)

2つの離れた文字列a,bについても、a+b>b+aから、aとbの間にあたる連結文字列cを考えると、a+c+b>b+c+aでないと最大の整数を得られないので、STLのソートを使って、

vector<string> use; //使う数字を文字列にしたもの(numbers全部1つずつとnumbersで一番大きいものをいくつか)
sort(use.begin(),use.end(),comp);

bool comp(string a, string b){
  return a+b>b+a;
}

として、連結した文字列を返せばよい。
嘘。