AGC057 B - 2A + x (700)
コンテスト中の考察
最小値が$ X以下なら0にできる
実際は$ X未満
全部二倍し、足す値について最大値では$ X未満、最小値では$ Xとすることで差が小さくなる
これを繰り返すと0にできる
最小値について二分探索する
二分探索内では$ A_iを操作して$ A_{n-1}との差を$ t以下にできるかを確かめる
判定がうまく行っていないらしく駄目
解説の解法
各$ A_iで操作をした結果作れる$ A_{n-1}以下の最大値と$ A_{n-1}以上の最小値$ l,rを求めておく
$ (l,r)のペアを$ lの昇順でソートする
各$ A_iの$ N+1通りで以下を行う
それ以前のものは$ rの値を使い、それより後のは$ lを使う
$ r - lで最小値を更新
これは前回までの$ rの最大値を使うことで各$ \mathcal{O}(1)になる
ソートがボトルネックで$ \mathcal{O}(N \log N)