ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - c278: 玩偶~玩偶~玩玩偶~ 解題心得

Not In My Back Yard | 2019-05-13 20:48:23 | 巴幣 0 | 人氣 141

題目連結:


題目大意:
第一列給定一正整數 N (2 ≦ N ≦ 10 ^ 5,且 N 必為偶數),代表有N個玩偶。每個玩偶有自己的「時尚度」。

第二列有 N 個正整數(皆介於 1 ~ 10 ^ 9),分別代表這 N 個玩偶的時尚度。試問,將玩偶兩兩配對成一組,則每一對玩偶時尚度可能有差。求每對的時尚度差之總和最小可為何?



範例輸入:
4
5 3 6 7


範例輸出:
3


解題思維:
因為每一對的差都要盡量小,才能使得總和最小。因此每一對的時尚度放在數線上的話就要盡量靠近。

因此,我們將給定的 N 個數字排序,即可達成以上需求。當排好以後,兩個兩個一組去求差值,最後再全部加總就是題目之所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作