SRM 346 Div1 Medium HeightRound

問題

N人の人がいて、それぞれの身長がheights[]で与えられる。これらを車座に配置した時に隣り合う身長差の最大値が最小化するような配置パターンを求めよ。複数あるときには身長差順で辞書式最小なものを返せ。

やりかた

単純に身長差順で配置すると最後の人と最初の人の部分でギャップが大きい。そのため下のような形で身長差順に配置していくと隣接する身長差がなるべく小さくなる。
⑨⑦⑤③①②④⑥⑧⑩

辞書式最小になるには①が筆頭に来るようにする。よって
①②④⑥⑧⑩⑨⑦⑤③

と並べ替えればいい。

以下ソース。

class HeightRound {
public:
  vector <int> getBestRound(vector <int> heights){
    int N = heights.size();
    sort(ALL(heights));
    if(N <= 3) return heights;

    vector<int> a, b;
    a.push_back(heights[0]);
    for(int i = 1; i < N; i++){
      if(i % 2 == 1) a.push_back(heights[i]);
      else b.push_back(heights[i]);
    }
    reverse(ALL(b));
    for(int i = 0; i < (int)b.size(); i++) a.push_back(b[i]);
    return a;
  }
};