主題
題目連結(jié)：
題目意譯：
數(shù)對(duì) (a,b) 的數(shù)對(duì)和等於 a + b 。最大數(shù)對(duì)和為數(shù)對(duì)列表中數(shù)對(duì)和之值最大的。
例如，如果我們有數(shù)對(duì) (1,5) 、 (2,3) 和 (4,4) ，則最大數(shù)對(duì)和為 max(1+5,2+3,4+4) = max(6,5,8) = 8 。
給定偶數(shù)長(zhǎng)度 n 的陣列 nums，將其元素們配對(duì)成 n ÷ 2 個(gè)數(shù)對(duì)使得
每個(gè) nums 中的元素恰好位於一個(gè)數(shù)對(duì)中，且
最大數(shù)對(duì)和盡可能地小。
回傳經(jīng)由最佳地配對(duì)元素後所得的最小之最大數(shù)對(duì)和之值。
限制：
n == nums.length
2 ≦ n ≦ 10 ^ 5
n is even.
1 ≦ nums[i] ≦ 10 ^ 5
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [3,5,2,3]
輸出： 7
解釋： 元素們可以配對(duì)成為數(shù)對(duì) (3,3) 和 (5,2) 。
最大數(shù)對(duì)和為 max(3+3, 5+2) = max(6, 7) = 7 。
範(fàn)例 2：
輸入： nums = [3,5,4,2,4,6]
輸出： 8
解釋： 元素們可以配對(duì)成為數(shù)對(duì) (3,5) 、 (4,4) 和 (6,2) 。
最大數(shù)對(duì)和為 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。
解題思維：
基本上跟這題（不過(guò)原題已經(jīng)設(shè)為未公開(kāi)了）一樣——將數(shù)字由小到大排序（大到小也可，總之要可以快速存取各種大小的順序），然後將最大與最小配對(duì)、次大與次小配對(duì)……以此類推。
而這樣便可以使最大數(shù)對(duì)和盡可能地小。原因如下：
令現(xiàn)在根據(jù)排序後所求得最大數(shù)對(duì)和的數(shù)對(duì)為 (x,y) ，其中 x ≦ y 。
接著我們假設(shè)排序的方法無(wú)法得到最佳解，因此存在一數(shù)對(duì) (s,t) 與 (x,y) （同樣不失一般性，令 s ≦ t）交換一個(gè)元素來(lái)使得最大數(shù)對(duì)和更小：
假設(shè)我們是將 s 與 x 項(xiàng)交換，因?yàn)橐屧?(x,y) 的最大總和更小，所以 s 應(yīng) ≦ x 而根據(jù)利用排序規(guī)則時(shí)配對(duì)（注意，我們還沒(méi)交換，所以 (s,t) 仍是排序配對(duì)的產(chǎn)物）可得 y ≦ t 。
再假設(shè) s = x - d ，則 t ≦ y + d 。因此 (x,t) 之?dāng)?shù)對(duì)和為 x + t ≦ x + y + d。而因?yàn)?s ≦ x 所以 d ≧ 0 ，進(jìn)而推得 x + y + d ≧ x + y = (x,y) 數(shù)對(duì)和。
因此 s 與 x 項(xiàng)交換反而可能更糟。同樣地，t 與 y 項(xiàng)交換也會(huì)得到類似的結(jié)論。
因此原本假設(shè)排序配對(duì)的方法無(wú)法得到最佳解的假說(shuō)是錯(cuò)的（得到了矛盾）。根據(jù)反證法可證得排序配對(duì)為最佳策略（之一）。
值得注意的是，上面的論述不會(huì)出現(xiàn) s 與 y 交換和 t 與 x 交換的情況，因?yàn)檫@樣的配對(duì)在以排序配對(duì)的前提下不可能出現(xiàn)。例如 s 與 y 交換代表著 x ≦ s ≦ y ≦ t ，但是光看這四個(gè)數(shù)字便可以知道在排序配對(duì)時(shí)我們至少應(yīng)得出 (x,t) 、 (s,y) 而非 (x,y) 、 (s,t) 。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
