切換
舊版
前往
大廳
主題

ZeroJudge - e542: 11054 - Wine trading in Gergovia 解題心得

Not In My Back Yard | 2019-11-23 11:23:58 | 巴幣 2 | 人氣 208

題目連結:


題目大意:
給定一正整數 n (2 ≦ n ≦ 100000,當 n = 0 時代表輸入結束),代表有 n 位居民。他們各自住在自己的房子,房子是排成一列的。

接著的一列有 n 個整數 ai(皆介於 -10000 ~ 10000 之間),代表葡萄酒的需求量。當 ai ≧ 0 ,代表該戶需求 |ai| 單位的葡萄酒;若 ai < 0 ,則代表該戶要販賣 |ai| 單位的葡萄酒。所有 ai 之值總和必為 0 。

而將一單位的葡萄酒從一間房子移到相鄰的房子需要一單位的工作量。試問,要滿足所有人的需求(將負責販賣的戶的酒移到需要那幾戶)需要多少單位的工作量?



範例輸入:
5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0


範例輸出:
9
9000


解題思維:
因為供需會抵消為 0 ,因此我們可以根據其目前的供給(需求)量來決定一次移動的工作量。

例如範例測資的 5 -4 1 -3 1:
5 -4 1 -3 1
一開始遇到一個 5 ,代表需要 5 單位葡萄酒。

5 -4 1 -3 1
再來碰到一個 -4 代表供給 4 單位葡萄酒,所以目前供需量為 5 - 4 = 1 ;工作量為 5 (不是抵銷後的數字,因為第一戶需要 5 單位,所以一定要從某處移過去。而現在我們移動了一格,所以加上 5)

5 -4 1 -3 1
接著碰到 1 ,供需量變為 1 + 1 = 2;工作量為 5 + 1 = 6。

5 -4 1 -3 1
接著碰到 -3 ,供需量變為 2 - 3 = -1 ;工作量變為 6 + 2 = 8 。

5 -4 1 -3 1
最後碰到 1 ,供需量為 -1 + 1 = 0 ;工作量變為 8 + |-1| = 8 + 1 = 9 。

所以總共需要 9 單位的工作量。而其他的供需分布也可以以上面的方式求出所求。

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

創作回應

更多創作