题目详情
返回题库题目描述
在一个国家的各个城市之间，需要进行物资的调配。给定一个整数n，表示这个国家的城市数量。再给定一列整数a1,a2,⋯,an，表示每个城市生产或者消费物资的数量——
- 正数表示对应城市是生产物资的，其绝对值代表产量；
- 负数表示对应城市是消费物资的，其绝对值代表消费量；
这些城市之间的道路网络呈一条直线，只有编号相邻的城市有道路相连。从某个城市搬运一个单位的物资到相邻城市将产生一个单位的工作量。请设计一个方案，使得每个城市需要的物资都能达成，且运输的总工作量达到最小。
输入数据保证生产总量和消费总量是相等的，即a1+a2+⋯+an=0。
输入描述
第一行：单个整数表示n。
第二行：n个整数表示a1,a2,⋯,an。
输出描述
单个整数：表示最优运输方案产生的最少工作总量。
数据范围
- 对于30%的数据，1≤n≤10；
- 对于60%的数据，1≤n≤100；
- 对于100%的数据，1≤n≤100000，−100000≤ai≤100000；