B. Sorted Adjacent Differences (Codeforces Round #633 Div. 2)

問題

https://codeforces.com/contest/1339/problem/B

問題概要

n個の整数からなる数列が与えられる。

この数列をとなるように並び替えよ。

考察

絶対値の差が広がるように並び替えろということです。これは元の数列をソートして、真ん中から左右に一つずつ取って並べていくことで構築可能です。そうすることで距離がどんどん遠くなっていきます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());
        if (n % 2 == 1) {
            cout << a[n / 2] << " ";
            for (int i = 1; i <= n / 2; i++) {
                cout << a[n / 2 - i] << " " << a[n / 2 + i] << (i == n / 2 ? '\n' : ' ');
            }
        } else {
            for (int i = 1; i <= n / 2; i++) {
                cout << a[n / 2 - i] << " " << a[n / 2 + (i - 1)] << (i == n / 2 ? '\n' : ' ');
            }
        }
    }
}