We should minimize the value of the function \(Nx-\sum_{i} (A_i-\min(2x,A_i))\). This function is convex downward, so a ternary search on \(x\) can do it. The complexity of this solution is \(O(N \log (\max(A_i)/\epsilon))\), where \(\epsilon\) is the error tolerance.

Alternatively, by considering the slope of the function, we can see that the function takes the minimum value at \(x=m/2\), where \(m\) is the median of \(A_i\). Thus, we can solve the problem in \(O(N\log N)\) time (by sorting \(A_i\) to find the median) or \(O(N)\) time (by using std::nth_element, for example).