e542. 11054 - Wine trading in Gergovia
Tags :
Accepted rate : 104人/107人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-28 14:56

Content

您可能會從漫畫"Asterix and the Chieftain's Shield"中了解到,Gergovia由一條街道組成,每個城市的居民都是葡萄酒推銷員。
您想知道這種經濟如何運作嗎?
每個人都從城市的其他居民那裡購買葡萄酒。每位居民每天都要決定要購買或出售多少酒。
有趣的是,供需始終是相同的,因此每個居民都能得到自己想要的東西。
但是有一個問題,將葡萄酒從一所房子運到另一所房子會導致工作量上升。
由於所有葡萄酒的品質都一樣,因此,Gergovia的居民不在乎與之交易的人,他們只對出售或購買特定數量的葡萄酒感興趣。
他們足夠聰明,可以找到一種交易方式,從而使運輸所需的總工作量最小化。
在這個問題上,您需要重建Gergovia的一天中的交易路線。為簡單起見,我們假設房屋是沿著一條直線建造的,相鄰房屋之間的距離相等
將一瓶葡萄酒從一棟房子運送到相鄰的房子需要一個單位的工作量。

Input

輸入包含多組測資。
每個測資第一行為一個整數n (2 ≤ n ≤ 100000),代表居民人數。
如果n = 0代表輸入結束。
下一行包含n個整數ai (-1000 ≤ ai ≤ 1000)。
如果ai ≥ 0,代表居住在第i個房屋中的居民要購買ai瓶葡萄酒。
如果ai < 0,則要出售ai瓶葡萄酒。
所有ai的總和為0。

Output

對於每組測資
輸出一行所需的最少幾單位的工作量以滿足每個居民的需求。

Sample Input #1
5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0
Sample Output #1
9
9000
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」