Slimes on a Line

Key Observation

Only the spread of the slimes matters:

$$R = \max_i a_i - \min_i a_i.$$

If all slimes are already at one position, then $R = 0$ and the answer is obviously $0$.

Otherwise, look at the leftmost and rightmost slimes. In one operation, the leftmost slime can move right by at most $1$, and the rightmost slime can move left by at most $1$. So the distance between them can shrink by at most $2$ per operation.

Therefore, if the initial range is $R$, we need at least

$$\left\lceil \frac{R}{2} \right\rceil$$

operations. That's the lower bound. Now we need to show it's not just a pessimistic math lecture.

Achieving the Bound

We can always choose $x$ between the current minimum and maximum. Then every slime to the left of $x$ moves right, and every slime to the right of $x$ moves left. So the extremes can be pulled inward by one step each operation.

After $k$ operations, no slime needs to move more than $k$ steps toward the final meeting point. We just need some integer position that is within distance $k$ of every initial slime. Such a position exists exactly when the intervals

$$[a_i - k,\ a_i + k]$$

all overlap.

Since every $a_i$ lies between $mn$ and $mx$, it is enough that

$$mn + k \ge mx - k,$$

which means

$$2k \ge mx - mn.$$

The minimum such $k$ is

$$\left\lceil \frac{mx - mn}{2} \right\rceil.$$

So the lower bound is achievable, and that is the answer. The middle slimes were just background extras.

Complexity

For each test case, scan the array once to find $mn$ and $mx$.

$$O(n)$$

time per test case and

$$O(1)$$

extra memory.