切換
舊版
前往
大廳
主題

ZeroJudge - c732: 神牛 解題心得

Not In My Back Yard | 2018-10-14 12:29:46 | 巴幣 0 | 人氣 151

題目連結:


題目大意:
給定一正整數N(N ≦ 10, 000,且保證N為偶數),代表接下來有N隻神牛。接下來的N行,每一行有正整數(一定小於10 ^ 9),代表這隻神牛的食量。

現將神牛兩兩一組,並讓當中食量總和最大的那一組的,盡可能令總和最小(最大值最小化)。

求最小值為何?



範例輸入:
【範例一】
4
1 5 2 8

【範例二】
6
1 2 3 4 5 6



範例輸出:
【範例一】
9

【範例二】
7



解題思維:
稍微觀察一下,不難發現:
只要先排序,然後食量最大的配上最小的,次大的配上次小的,看哪一組最大,即是最小化後的最大值。

這點可以在【範例二】很清楚地了解到。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作