UVa11054 Gergovia的酒交易(數學歸納法)

lonelyprince7 2021-08-15 11:48:46 阅读数:555

本文一共[544]字,预计阅读时长:1分钟~
uva11054 uva gergovia 交易

直線上有\(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\)的遞推關系式可以錶述如下:

\[\begin{equation} ans_i = \left\{ \begin{matrix} |A_i| , \quad i = 1 \\ ans_{i - 1} + |last_i|, \quad 1 \leqslant i \leqslant n \end{matrix} \right. \end{equation} \]

如果你覺得以上的數學式子還是過於抽象,那麼可以繼續看下面代入值計算的例子。我們設村莊數量為\(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)
版权声明:本文为[lonelyprince7]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815114841288e.html