UVa11054 Gergovia的酒交易(数学归纳法)
UVa11054 Gergovia的酒交易(数学归纳法)
直线上有n个等距村庄，每个村庄要么买酒，要么卖酒。设第i个村庄对酒的需求为Ai(−1000⩽Ai⩽1000)，其中Ai>0表示买酒，Ai<0表示卖酒。所有村庄供需平衡，即所有Ai之和等于0。
把k个单位的酒运到相邻村庄去需要k个单位的劳动力，问最少需要多少劳动力才能满足所有的村庄的要求。输出保证在64位带符号整数范围内。
输入输出样例
输入
55 -4 1 -3 16-1000 -1000 -1000 1000 1000 10000
输出
99000
题解
这题可以采用数学归纳法的角度进行思考，
首先，我们先看基准情形，第1个村庄对酒的需求为Ai(可能需要买，可能需要卖)。那么，不管是买酒还是卖酒，都需要第1个村庄和第2∼n个村庄之间存在大小为|Ai|的酒搬运(可能酒交易的双方并不是第1个村庄和第2个村庄，但是必须经由这两个村庄)。
接下来我们开始归纳，我们设lasti=∑j=ij=1Aj表示第1∼i个村庄对酒的总需求（可能需要买，可能需要卖）。那么，不管是买酒还是卖酒，都需要第i个村庄和第i+1个村庄之间存在大小为|lasti|的酒搬运(可能部分酒交易的双方并不是第i+1和i个村庄，但是必须经由这两个村庄)。我们用ansi表示第1∼i个村庄需要的总搬运需求。
综上，ansi的递推关系式可以表述如下：
ansi={|Ai|,i=1ansi−1+|lasti|,1⩽i⩽n(1)
如果你觉得以上的数学式子还是过于抽象，那么可以继续看下面代入值计算的例子。我们设村庄数量为n=4，村庄1∼4的酒需求分别是−3,+4,−5,+4，那么我们模拟算法的过程如下图所示：
可以看到，最后求得的4个村庄的总共搬运劳动力ans4=8。
我们再看村庄1∼4的酒需求分别是+3,−4,+5,−4的情况。由上面的推导可知，这种情况其实只是把每个村庄的买卖情况取反了，但最后的总搬运量不变。我们模拟算法的过程如下图所示：
可以看到，最后求得的4个村庄的总共搬运劳动力和上面的情况一样，仍然是ans4=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)