Elevator Against Humanity

A false instinct here is to simulate elevator decisions or DP over boarded people. That is dead on arrival: the set of passengers can be enormous. The elevator capacity is mostly a distraction. What matters is the order in which the $2n$ special floors are visited.

Sign view

Let the visited floors be $x_1, x_2, ..., x_{2n}$. The only validity rule is that every $s_i$ appears before its matching $f_i$. The time is

$t = |x_1-1| + |x_2-x_1| + ... + |x_{2n}-x_{2n-1}|$.

Since all floors are above $1$, the first term is $x_1-1$. Every later absolute value contributes one endpoint with a plus sign and one endpoint with a minus sign. So, ignoring the constant $-1$:

• there are $2n$ plus signs,
• there are $2n-1$ minus signs,
• every floor except the last appears twice,
• the last floor appears once,
• the last floor must be some destination $f_i$.

So the problem becomes: choose the final destination and assign signs as profitably as possible. Weird? Yes. Useful? Very.

Best signs for a fixed final floor

Sort all floors:

$y_1 < y_2 < ... < y_{2n}$.

Call $y_1...y_n$ the low half and $y_{n+1}...y_{2n}$ the high half. Let

$L = y_1 + ... + y_n$, $H = y_{n+1} + ... + y_{2n}$.

If we temporarily ignore precedence, the best sign assignment is obvious: put plus signs on the biggest copies and minus signs on the smallest copies.

Suppose the final floor is $y_k$.

If $k <= n$, one low copy is missing because $y_k$ appears once instead of twice. Then all high copies get plus signs, all low copies get minus signs, and $y_k$ has coefficient $-1$ instead of $-2$:

$t = -1 - 2L + y_k + 2H$.

If $k > n$, one high copy is missing. There are only $2n-1$ high copies, so one plus sign must go to the largest low floor, $y_n$. Thus $y_n$ has coefficient $0$, the final $y_k$ has coefficient $+1$, and the formula is

$t = -1 - 2L + 2y_n + 2H - y_k$.

These are upper bounds for any real route, because no route can beat the best possible sign assignment.

When a high-half start exists

If at least one starting floor lies in the high half, those upper bounds are actually reachable.

The sign pattern wants an alternating route between high and low floors. High floors become local maxima with coefficient $+2$, low floors become local minima with coefficient $-2$, and the final floor gets only one sign. Starting from a high-half starting floor gives the walk the correct first move.

What about precedence? If the next desired floor is legal, take it. If all desired floors on the other side are illegal destinations, then their matching starts are still on the current side, so board one of those starts instead and continue. This local repair keeps the alternation alive. The elevator is evil, but not magic.

Therefore, in this case we just try every destination rank $k$ and take the corresponding formula above.

The all-up case

Now assume there is no high-half start. Since there are exactly $n$ starts total, this means all starts are in the low half and all destinations are in the high half.

Now the route must start at a low floor and finish at a high floor. The best alternating route would like to start at the largest low floor $y_n$ and finish at the smallest high floor $y_{n+1}$, giving

$t = -1 - 2L + 2y_n + 2H - y_{n+1}$.

This is valid if $y_n$ and $y_{n+1}$ belong to different people. Start at $y_n$, eventually board the person whose destination is $y_{n+1}$, and finish there.

If $y_n$ and $y_{n+1}$ are the same person, that perfect boundary choice breaks: after starting at $y_n$, the only immediately deliverable high floor is $y_{n+1}$, which we wanted to save for the end. So we must compromise. There are only three optimal-looking compromises:

1. Start at $y_{n-1}$ and finish at $y_{n+1}$:

$t = -1 - 2L + 2y_{n-1} + 2H - y_{n+1}$.

2. Start at $y_n$ and finish at $y_{n+2}$:

$t = -1 - 2L + 2y_n + 2H - y_{n+2}$.

3. Start at $y_n$, first move downward, and finish at $y_{n+1}$ from above:

$t = -1 - 2L + 4y_n + 2H - 3y_{n+1}$.

Take the maximum of these three. For $n=1$, there is no boundary juggling: the only route is $1 -> s_1 -> f_1$.

Implementation

Sort the $2n$ floors, keeping whether each floor is a start or finish and its person id. Compute $L$ and $H$ with prefix sums.

Then:

• if some start is in positions $n+1...2n$, iterate over all destination floors and apply the fixed-final formulas;
• otherwise handle the all-up case with the boundary formulas.

Sorting dominates, so the complexity is $O(n log n)$ per test case, with $O(n)$ memory. The sum of $n$ is $10^5$, so this cruises.