主題

ZeroJudge - b858: 橘子 解題心得

Not In My Back Yard | 2021-02-10 00:00:01 | 巴幣 0 | 人氣 40

題目連結:


題目大意:
輸入第一列給定一正整數 T (T ≦ 10),代表有 T 筆測試資料,每筆佔兩列。測資第一列給定一正整數 N (N ≦ 100),代表有 N 顆橘子;第二列給定 N 個正整數(皆不超過 1000),代表每顆橘子要榨汁所需之時間。

現在吉吉有一台榨汁機,該機器一次可以榨兩顆橘子。試問將給定的 N 顆橘子搾完汁最少需要多少時間?



範例輸入:
2
3
1 2 3
4
1 4 2 3


範例輸出:
3
5


解題思維:
榨汁機一次可以搾兩顆橘子,因此我們將其中一邊叫 A 搾汁端、一邊叫 B 搾汁端。

時間花最少的解法必是 A 、 B 兩端不停歇地搾汁直到沒有橘子可以搾的時候。所以因此我們把兩邊花的時間叫做 TA 以及 TB,而所有橘子的搾汁時間之總和定為 T。

而總時間要最少應滿足 TA 跟 TB 要盡量地接近,也就是我們要使用取這 N 顆橘子各自的時間想辦法湊到盡量接近 T ÷ 2 ,才會使得 TA 以及 TB 盡量地靠近。

所以本題就變成了換硬幣題目之變型,如這題




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

創作回應

更多創作