最小化すべき関数は，\(Nx-\sum_{i} (A_i-\min(2x,A_i))\) です． ここで，この関数は下に凸な形をしているので，\(x\) で三分探索をすれば解くことができます． この場合の計算量は，\(O(N \log (\max(A_i)/\epsilon))\) になります． ここで，\(\epsilon\) は許容誤差です．

なお，点 \(x\) における関数の傾きを考えると，\(A_i\) の中央値を \(m\) とすれば，\(x=m/2\) で関数の値が最小化されるとわかります． よって，許容誤差に依存せずに，\(O(N\log N)\) （\(A_i\) をソートして中央値を求めた場合）または \(O(N)\) （std::nth_element などを用いる）でこの問題を解くことができます．