链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1995
题意：
直线上有n（2≤n≤100000）个等距的村庄，每个村庄要么买酒，要么卖酒。设第i个村庄对酒的需求为ai（-1000≤ai≤1000），其中ai>0表示买酒，ai<0表示卖酒。所有村庄供需平衡，即所有ai之和等于0。把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。计算最少需要多少劳动力可以满足所有村庄的需求。输出保证在64位带符号整数的范围内。
分析：
问题等价转换。考虑最左边的村庄。如果需要买酒，即a1>0，则一定有劳动力从村庄2往左运给村庄1，而不管这些酒是从哪里来的（可能就是村庄2产的，也可能是更右边的村庄运到村庄2的）。这样，问题就等价于只有村庄2～n，且第2个村庄的需求为a1+a2的情形。不难发现，ai<0时这个推理也成立（劳动力同样需要|ai|个单位）。
代码：
1 #include <cstdio> 2 #include <cstdlib> 3 4 int main(){ 5 int n; 6 while(scanf("%d", &n) && n){ 7 int need; 8 scanf("%d", &need); 9 long long last = need, ans = abs(need); 10 for(int i = 1; i < n; i++){ 11 scanf("%d", &need); 12 last += need; 13 ans += abs(last); 14 } 15 printf("%lld\n", ans); 16 } 17 return 0; 18 }
转载于:https://www.cnblogs.com/hkxy125/p/8053031.html
