Problem 4107 --H: 拔河

4107: H: 拔河

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

小明是学校里的一名老师,他带的班级共有 n 名同学,第 i 名同学力量值 为 ai。在闲暇之余,小明决定在班级里组织一场拔河比赛。 为了保证比赛的双方实力尽可能相近,需要在这 n 名同学中挑选出两个队 伍,队伍内的同学编号连续:

{al1 , al1+1, ..., ar1−1, ar1 } 和 {al2 , al2+1, ..., ar2−1, ar2 },其 中 l1 ≤ r1 < l2 ≤ r2。 

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

输入共两行。 第一行为一个正整数 n。 第二行为 n 个正整数 ai。
输出共一行,一个非负整数,表示两个队伍力量值之和的最小差距。 
5
10 9 8 12 14
1

其中一种最优选择方式: 队伍 1:{a1, a2, a3},队伍 2:{a4, a5},力量值和分别为 10 + 9 + 8 = 27, 12 + 14 = 26,差距为 |27 − 26| = 1。 


【评测用例规模与约定】 

对于 20% 的评测用例,保证 n ≤ 50。 对于 100% 的评测用例,保证 n ≤ 103,ai ≤ 109

推荐代码 查看4107 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$2 $ms] 纪润奇 1097550 2024-04-23 21:22:36
内存最少[$2176 $KB] 纪润奇 1097550 2024-04-23 21:22:36
第一AC 纪润奇 1097550 2024-04-23 21:22:36
第一挑战 纪润奇 1097550 2024-04-23 21:22:36

赛题来源/所属竞赛 第十五届蓝桥杯大赛软件赛省赛B组 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛