D - Shocking Arrangement

問題

数列 $a$ が与えられる。
うまく並び替えて、

$\max_{1 \le l \le r \le n}|a_l + \dots + a_r| < \max(a_1, \dots, a_n) - \min(a_1, \dots, a_n)$

とできるか？
できるならその並び方を出力。

制約

• $1 \le n \le 300000$
• $-10^9 \le a_i \le 10^9$
• $\sum a_i = 0$

考察

まず、 $\max, \min$ は固定される。
$\max, \min$ が同符号 or 0 なら、存在しない。というのも、正の場合 $\max \ge \max - \min$ 、負の場合 $|\min| = -\min \ge \max - \min$ が成り立ってしまうので。
(制約で $\sum a_i = 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;
}