Villagers

The statement has one trap: Steve does not need to make every pair directly friends. He only needs the friendship graph to be connected. So we want a cheap connected graph, not a complete graph. Big difference. One is sane; the other is financial crimes.

Suppose two current grumpiness values are $x \le y$.

The operation costs:

$$y$$

and the new values become:

$$0,\ y-x$$

So every positive-positive operation creates at least one villager with grumpiness $0$.

That matters because if two components each contain a $0$ villager, Steve can connect those two components for free: choose the two zero-grumpiness villagers, pay $\max(0,0)=0$, and add a friendship edge.

So the real goal is:

Make every villager belong to some component that contains a zero-grumpiness villager. Then connect those components together for free.

Turning the problem into pairing

Look at any villager before their first operation. Their grumpiness has not changed yet, so it is still their original value $g_i$.

For a villager's first useful operation, there are two possibilities.

1. They are paired with another not-yet-handled villager.

If their values are $x$ and $y$, this costs $\max(x,y)$, and both villagers end up in a component containing a zero. Great: one operation handles two villagers.

2. They are connected to an already handled component.

That component already has a zero villager, so the cheapest way is to connect this villager to that zero. If their value is $x$, this costs $x$.

Using a nonzero villager from that component cannot be cheaper, because the operation would cost at least $x$ anyway. So no magic discount hiding there.

Therefore the paid operations are equivalent to this simpler problem:

• split villagers into pairs, where a pair $(x,y)$ costs $\max(x,y)$;
• if $n$ is odd, one villager may be left alone, costing its own value;
• minimize the total cost.

There is no reason to have two singletons, because paying $x+y$ for two singletons is never better than pairing them for $\max(x,y)$. So:

• if $n$ is even, everyone is in a pair;
• if $n$ is odd, exactly one singleton remains.

How to pair optimally

Sort the values:

$$a_1 \le a_2 \le \cdots \le a_n$$

The key greedy fact is: in an optimal grouping, the two largest remaining values can be paired together.

Why?

Let the largest be $a_n$ and the second largest be $a_{n-1}$.

If $a_n$ is paired with some smaller value $x$, and $a_{n-1}$ is paired with $y$, then the old cost from those two groups is:

$$a_n + a_{n-1}$$

If we instead pair $a_n$ with $a_{n-1}$, that group still costs $a_n$. Then pair $x$ with $y$, which costs at most $a_{n-1}$ because both are no larger than $a_{n-1}$.

So the cost does not increase.

If $a_n$ or $a_{n-1}$ was the singleton in the odd case, the same swap works: make $(a_{n-1}, a_n)$ a pair, and the smaller displaced value becomes the singleton. Again, cost does not increase.

So we can always pair the two largest, remove them, and repeat.

That gives:

• for even $n$: pay $a_n + a_{n-2} + a_{n-4} + \cdots + a_2$;
• for odd $n$: pay $a_n + a_{n-2} + a_{n-4} + \cdots + a_1$.

In other words, after sorting, sum every other element, starting from index:

• $1$ in 0-indexing if $n$ is even;
• $0$ in 0-indexing if $n$ is odd.

Construction check

For even $n$, pair:

$$(a_1,a_2), (a_3,a_4), \ldots, (a_{n-1},a_n)$$

Each pair costs its larger value, so the total is:

$$a_2+a_4+\cdots+a_n$$

Each pair creates a zero-grumpiness villager. Then connect all those zero villagers together for free.

For odd $n$, leave $a_1$ alone first, and pair:

$$(a_2,a_3), (a_4,a_5), \ldots, (a_{n-1},a_n)$$

Then connect $a_1$ to any zero-grumpiness villager, costing $a_1$. Total:

$$a_1+a_3+a_5+\cdots+a_n$$

That matches the formula.

Complexity

Sorting dominates:

$$O(n \log n)$$

per test case, with total $n \le 2 \cdot 10^5$, easily fine.