\(Nx - \sum_i (A_i - \min(2x, A_i))\) という関数を最小化する \(x\) を求めたいです。

上の関数は直線と折れ線の和であって、折れ線の角は \(A_i/2\) です。そのため、それらの和も \(A_i/2\) で折れ曲がるグラフになっています。

つまり、最小値としてあり得る \(x\) はその角、\(A_i/2\) です。 予め \(A\) をソートしておくと、\(x = A_i/2\) のとき、

\(\sum_j \min(2x, A_j) = \sum_{j < i} A_j + \sum_{i \le j} 2x\)

なります。これは、\(\sum_{j < i} A_j\) を持ちながら \(i\) を昇順に試していくことで \(O(1)\) で求めることができます。ソートする部分がボトルネックとなり、計算量は \(O(N \log N)\) です。

(さらに考察すると、公式解説の通り最小値を取る \(x\) が中央値になっていることがわかりますが、そのことを考えなくとも全部の候補を高速に試すことができます)