蓝桥杯2024年第十五届省赛真题-拔河

小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续:{a_l1, a_l1+1, ..., a_r1−1, a_r1} 和 {a_l2, a_l2+1, ..., a_r2−1, a_r2}，其中 l₁ ≤ r₁ < l₂ ≤ r₂。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入共两行。

第一行为一个正整数 n。

第二行为 n 个正整数 a_i。

5
10 9 8 12 14

1

【样例说明】

其中一种最优选择方式：队伍 1：{a₁, a₂, a₃}，队伍 2：{a₄, a₅}，力量值和分别为 10 + 9 + 8 = 27，12 + 14 = 26，差距为 |27 − 26| = 1。

【评测用例规模与约定】

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

对于 100% 的评测用例，保证 n ≤ 10³，ai ≤ 10⁹。