Let's observe the function ~f(x)~ where ~x~ represents the height of the middle column (the one with the minimal height) which tells us the number of minimal moves necessary to rearrange the piles in the described way. We can calculate this because then the minimal number of moves is uniquely determined: if a column has more bricks than necessary, we need to remove them and if it is missing bricks, we need to add new bricks.

We have two piles, but it is stated that in the end the corresponding columns have to be of equal heights. Then Mirko's pile is ~f1(x) = |c_{m1}-x| + |c_{m2}-x| + \dots + |c_{mn}-x|~ and Slavko's pile is ~f2(x) = |c_{s1}-x| + |c_{s2}-x| + \dots + |c_{sn}-x|~ where ~c_{m1}, c_{m2}, \dots, c_{mn}~ and ~c_{s1}, c_{s2}, \dots, c_{sn}~ are constants which depend on the height and position of the column.

If we observe the graph of the function ~(f1+f2)(x)~ we will notice that the function is decreasing at first, then increasing and it has only one global minimum.

It is easily noticed that this minimum is exactly the first point ~m~ for which the following holds: ~(f1+f2)(m) < (f1+f2)(x+1)~. In other words, it is the point where the function starts to increase. Also, we can notice that for every point to the left of ~m~ the following holds: ~(f1+f2)(x) > (f1+f2)(x+1)~ and for every point to the right of ~m~: ~(f1+f2)(x) < (f1+f2)(x+1)~. This is why we can locate point ~m~ using binary search, by comparing the relation of function values of two adjacent points.

Alternative approach

(Bruce Merry)

The first trick is to notice that the slightly odd target shape can be removed from the problem: simply subtract ~|i - \frac N 2|~ from element ~i~ of the inputs (the shortest target shape) and now solve for a flat target. You have ~2N~ numbers and need to find the ~m~ such that ~sum(|a_i-m|)~ is minimised. This is just the median of the numbers (exercise: prove this, if you don't already know why). The median can be found in ~\mathcal O(N)~ time using std::nth_element; a binary search is also fast enough.