3121: 环型运输
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
某个国家有若干个城市，每个城市生产或者消费一定量的物资，已知国家的生产和消费的总量恰好是相等的。假设这些城市呈环状排列，请问如何设计一个最佳的运输计划？
给定一个圆环序列 �1,�2,⋯,��a1,a2,⋯,an，保证
�1+�2+⋯+��=0a1+a2+⋯+an=0
定义一次移动操作可以任意选取两个相邻的元素以及一个大于 00 的移动量 ΔΔ，将其中一个元素减去 ΔΔ，另一个元素增加 ΔΔ。由于是圆环序列，所以 ��an 和 �1a1 也算作两个相邻的元素。
请设计一个不断进行移动操作的方案，使得最后元素全部变成 00，且过程中移动量的总和最小。
输入
第一行：单个整数表示 �n。
第二行：�n 个整数表示 �1,�2,⋯,��a1,a2,⋯,an。
第二行：�n 个整数表示 �1,�2,⋯,��a1,a2,⋯,an。
- 对于 30%30% 的数据，1≤�≤101≤n≤10；
- 对于 60%60% 的数据，1≤�≤1001≤n≤100；
- 对于 100%100% 的数据，1≤�≤1051≤n≤105，−104≤��≤104−104≤ai≤104；
输出
单个整数：表示修改成全 00 的最少移动总量。
样例输入 复制
4
10 20 -20 -10样例输出 复制
30