ACM-ICPC-OJ训练营

问题 3164 --试题 H: 拔河

3164: 试题 H: 拔河

时间限制: 1 Sec 内存限制: 256 MB
提交: 0 解决: 0
[提交][状态][讨论版][命题人:]

题目描述

小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为a_i。在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续:{a_l1 , a_l1+1, ..., a_r1−1, a_r1 } 和 {a_l2, a_l2+1, ..., ar_2−1, a_r2}，其中 l₁ ≤ r₁< l₂ ≤ r₂。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入描述

输入共两行。
第一行为一个正整数 n。
第二行为 n 个正整数 a_i。

输出描述

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

样例输入

5
10 9 8 12 14

样例输出

提示

其中一种最优选择方式：

队伍 1：{a₁, a₂, a₃}，队伍2：{a_4, a₅}，力量值和分别为10+ 9 + 8 = 27，12+ 14 = 26，差距为|27 −26| = 1。

对于20%的评测用例，保证 n ≤ 50。

对于100%的评测用例，保证 n ≤ 10
3，a_i ≤ 10
9。

来源

第十五届蓝桥杯省赛B组

[提交][状态]