直线上有\(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\)的递推关系式可以表述如下：
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)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/11795.html
