gergovia的交易tijie

题目详情

直线上有nn个等距村庄，每个村庄要么买酒，要么卖酒。设第ii个村庄对酒的需求为

AiAi(−1000⩽Ai⩽1000−1000⩽Ai⩽1000)，其中Ai>0Ai>0表示买酒，Ai<0Ai<0表

示卖酒。所有村庄供需平衡，即所有AiAi之和等于0。

把kk个单位的酒运到相邻村庄去需要kk个单位的劳动力，问最少需要多少劳动力才能满足所有的村

庄的要求。输出保证在64位带符号整数范围内。

输入格式

5
5 -4 1 -3 1
​​​​​​​6
-1000 -1000 -1000 1000 1000 1000
0

输出 

9
9000

​​​​​​​

思路

考虑最左边的村庄，买酒则a1>0，则一定劳动力从村庄2往左运给村庄1，而不管这些酒是从哪里来的(可能是村庄2产的也有可能是右边村庄的 )。这样，问题就等价于只有村庄2-n，且第二个村庄的需求为a1+a2的情形。不难发现，ai<0时这个推理也成立（劳动力同样需要ai个单位）

代码

#include<iostream>


int main()
{

int n;
while(cin>>n&&n)
{long long ans=0,a,last=0;
for(int i=0;i<n;i++)
{
cin>>a;
ans+=abs(last);
last+=a;

}
cout<<ans<<"\n";}
return 0;
}