直線上有\(n\)個等距村莊，每個村莊要么買酒，要么賣酒，設第\(i\)個村莊對酒的需求為\(A_i\)(\(-1000 \leqslant A_i \leqslant 1000\))，其中\(A_i>0\)表示買酒，\(A_i<0\)表示賣酒，所有村莊供需平衡，即所有\(A_i\)之和等于0，
把\(k\)個單位的酒運到相鄰村莊去需要\(k\)個單位的勞動力，問最少需要多少勞動力才能滿足所有的村莊的要求，輸出保證在64位帶符號整數范圍內，
輸入輸出樣例
輸入
5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0
輸出
9
9000
題解
這題可以采用數學歸納法的角度進行思考，
首先，我們先看基準情形，第\(1\)個村莊對酒的需求為\(A_i\)(可能需要買，可能需要賣)，那么，不管是買酒還是賣酒，都需要第\(1\)個村莊和第\(2 \sim n\)個村莊之間存在大小為\(|A_i|\)的酒搬運(可能酒交易的雙方并不是第\(1\)個村莊和第\(2\)個村莊，但是必須經由這兩個村莊)，
接下來我們開始歸納，我們設\(last_i = \sum_{j=1}^{j=i}A_j\)表示第\(1 \sim i\)個村莊對酒的總需求（可能需要買，可能需要賣），那么，不管是買酒還是賣酒，都需要第\(i\)個村莊和第\(i+1\)個村莊之間存在大小為\(|last_i|\)的酒搬運(可能部分酒交易的雙方并不是第\(i+1\)和\(i\)個村莊，但是必須經由這兩個村莊)，我們用\(ans_i\)表示第\(1 \sim i\)個村莊需要的總搬運需求，
綜上，\(ans_i\)的遞推關系式可以表述如下：
如果你覺得以上的數學式子還是過于抽象，那么可以繼續看下面代入值計算的例子，我們設村莊數量為\(n=4\)，村莊\(1 \sim 4\)的酒需求分別是\(-3, +4, -5, +4\)，那么我們模擬演算法的程序如下圖所示：
可以看到，最后求得的4個村莊的總共搬運勞動力\(ans_4 = 8\)，
我們再看村莊\(1 \sim 4\)的酒需求分別是\(+3, -4, +5, -4\)的情況，由上面的推導可知，這種情況其實只是把每個村莊的買賣情況取反了，但最后的總搬運量不變，我們模擬演算法的程序如下圖所示：
可以看到，最后求得的4個村莊的總共搬運勞動力和上面的情況一樣，仍然是\(ans_4 = 8\)，由此可得，我們的演算法正確，演算法的Python代碼實作如下：
while True:
n = int(input())
if n == 0:
break
A = list(map(int, input().strip().split()))
ans, last = 0, 0
for i in range(n):
last += A[i]
ans += abs(last)
print(ans)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294372.html
標籤：其他
下一篇：阿里云NAS檔案遷移專案實踐