[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; }
ディスカッション
コメント一覧
まだ、コメントがありません