分数: 300 点
问题陈述
由于 KEYENCE 总部的员工越来越多,他们决定将总部各部门分成两组,并错开午休时间。
KEYENCE 总部有 N 部门,以及人员数量 i第部门 (1\leq i\leq N) is K_i.
将每个部门分配到组时 A 或组 B,让各组同时午休,并保证各组的午休时间 A 和组 B 不重叠,求同时午休的最大人数的最小可能值。
换句话说,找到以下较大者的最小可能值:分配给组的部门的总人数 A,以及分配到组的部门的总人数 B.
约束
- 2 \leq N \leq 20
- 1 \leq K_i \leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K_1 K_2 \ldots K_N
输出
打印同时午休的最大人数的最小可能值。
示例输入 1
5 2 3 5 10 12
示例输出 1
17
分配部门时 1, 2,和 5 到群组 A和部门 3 和 4 到群组 B,组 A 共有 2+3+12=17 人和组 B 共有 5+10=15 人。因此,同时午休的最大人数为 17.
不可能分配部门以使两个组都有 16 或者更少的人,所以打印 17.
示例输入 2
2 1 1
示例输出 2
1
多个部门可能有相同数量的人员。
示例输入 3
6 22 25 26 45 22 31
示例输出 3
89
例如,分配部门时 1, 4,和 5 到群组 A和部门 2, 3,和 6 到群组 B,同时午休的最大人数为 89.