Problem#
有 2n 組數對 [a_i, b_i] 今天挑 $n$ 個 $a_i$ 相加，剩下的 $n$ 的 $b_i$ 相加，問你出來值最小多少?
想法#
直覺想法 按照大小 sort 接著從小的開始挑，但是 $b$ 就不保證是小的，有個想法是把每組 $(a_i, b_i)$ 變成 $x_i = a_i - b_i$，如果 $x$ 比較小，代表該數對的 $a$ 較大；如果 $x$ 比較大，代表該數對的 $b$ 較大。
按照 $a_i - b_i$ sort 之後，從小的開始挑 $n$ 個 + a，接著再挑 $n$ 個 + b 即可。
- 時間複雜度: $\mathcal{O}(n\log{n})$ (sort)
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
心得#
一開始沒想到可以用相差來化簡大小比較，看了題解才有想法QQ