[Codeforces] Codeforces Round #726 (Div. 2) C. Challenging Cliffs

問題

方針

\( h \) を昇順に整列させて考えます.\( h_{i + 1} -h_{i} \) を最小化する最小の \( i \) を \( j \) とします.ここで,\( h_j \) を先頭にして,\( h_{j+1} \) を末尾に配置します.このとき,

\[ h_{j}, h_{j+2}, h_{j+3}, \cdots, h_{n}, h_{1}, h_{2}, \cdots, h_{j-1}, h_{j+1}\]

と並べることで少なくとも \( n -2 \) の難易度が保証されます.\( n -1 \) の難易度となるときは全ての山の高さが同じであるときなので,これが答えとなります.

コード

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

int n;
ll h[200000];

void solve() {
    sort(h, h + n);
    int id = 0;
    for (int i = 0; i < n - 1; i++) {
        if (h[id + 1] - h[id] > h[i + 1] - h[i]) {
            id = i;
        }
    }
    cout << h[id] << " ";
    for (int i = id + 2; i < n; i++) {
        cout << h[i] << " ";
    }
    for (int i = 0; i < id; i++) {
        cout << h[i] << " ";
    }
    cout << h[id + 1] << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> h[j];
        }
        solve();
    }
    return 0;
}