642. Pairing Up for the Best Total of Minimums
An even number of values is given. Split them into pairs, and score each pair by its SMALLER value. Arrange the pairs so that the total score is as large as possible.
Print that largest total.
1 4 3 2 -> 4 pairs (1,2) and (3,4), scoring 1 + 3
6 2 6 5 1 2 -> 9 pairs (1,2) (2,5) (6,6), scoring 1 + 2 + 6
10 1 10 1 -> 11
## Every pair wastes its larger value
Each pair contributes only its smaller value, so exactly half the values are thrown away. The question is which half, and the answer is: make the discarded ones as cheap as possible by pairing each value with its nearest neighbour.
## Sort and take every other one
sort ascending
answer = a[0] + a[2] + a[4] + ...
Pairing adjacent values (a[0],a[1]), (a[2],a[3]) and so on scores the even-indexed ones.
## Why adjacent pairing is optimal
The largest value is discarded whatever happens, since whatever it is paired with is smaller. So pair it with the SECOND largest, which loses the least: that makes the second largest the discarded partner rather than something smaller that could have scored.
Formally, suppose an optimal pairing puts the two largest values p and q with different
partners u and v. The score from those two pairs is u + v, since p and q are the
largest. Re-pair them as (p,q) and (u,v): the score becomes min(p,q) + min(u,v), which is
at least max(u,v) + min(u,v) = u + v, because min(p,q) is at least as large as both u and
v.
So the swap never loses, the two largest can always be paired together, and the argument repeats on what remains.
## Why the "two pointers" are the index step
After sorting, the pairing is (0,1), (2,3), and so on: two cursors moving together, one on
each member of the pair. The loop collapses to stepping by two, which is what that structure
looks like once it is understood.
Writing it as i = 0, j = 1 advancing both by 2 is the same thing said longer.
## Overflow
Half of 200000 values near 10^9 gives a total near 10^14. Use 64 bits.
## Boundaries
Two values score the smaller of them. All values equal score n/2 copies of that value.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `2 ≤ n ≤ 200000` and `n` is even - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an even integer n.
The second line contains n integers.
Output
Print one integer, the largest achievable total of the pair minimums.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.