問題
数列 が与えられる。
うまく並び替えて、
とできるか?
できるならその並び方を出力。
制約
考察
まず、 は固定される。
が同符号 or 0 なら、存在しない。というのも、正の場合 、負の場合 が成り立ってしまうので。
(制約で になってるので、同符号ってことはないことに終了後気づいた)
それ以外なら可能。こんなイメージ。
愚直に、減らしてオーバーしないなら減らす、増やしてオーバーしないなら増やす、を繰り返す。
コード
https://codeforces.com/contest/1798/submission/199287581
void solve() { int n; cin >> n; vector<int> a(n); rep(i, n) cin >> a[i]; ll x = *max_element(a.begin(), a.end()); ll y = *min_element(a.begin(), a.end()); if (x * y >= 0) { cout << "No" << endl; return; } cout << "Yes" << endl; sort(a.begin(), a.end()); deque<int> b; rep(i, n) b.push_back(a[i]); ll sum = 0, z = x - y; rep(i, n) { if (abs(sum + b.front()) < z) { sum += b.front(); cout << b.front() << " "; b.pop_front(); } else if (abs(sum + b.back()) < z) { sum += b.back(); cout << b.back() << " "; b.pop_back(); } else { assert(false); } } cout << endl; }