AT_abc374_c [ABC374C] Separated Lunch

题目描述

由于 Keyence 总公司的员工人数不断增加，公司决定将总部的所有部门分成两组，并分别安排不同的午休时间段。

Keyence 总公司共有 $N$ 个部门，第 $i$ 个部门有 $K_i$ 人。

请将每个部门分配到组 $A$ 或组 $B$ 中，使得每组的部门可以同时午休，并且组 $A$ 和组 $B$ 的午休时间不重叠。请你求出在所有可能的分组方式中，同时午休的最大人数的最小可能值。
也就是说，设组 $A$ 的总人数为 $S_A$，组 $B$ 的总人数为 $S_B$，请你最小化 $\max(S_A, S_B)$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K_1$ $K_2$ $\ldots$ $K_N$

输出格式

请输出同时午休的最大人数的最小可能值。

输入输出样例 #1

输入 #1

5
2 3 5 10 12

输出 #1

17

输入输出样例 #2

输入 #2

2
1 1

输出 #2

1

输入输出样例 #3

输入 #3

6
22 25 26 45 22 31

输出 #3

89

说明/提示

限制条件

• $2 \leq N \leq 20$
• $1 \leq K_i \leq 10^8$
• 所有输入均为整数

样例解释 1

将第 $1,2,5$ 个部门分配到组 $A$，第 $3,4$ 个部门分配到组 $B$ 时，组 $A$ 的总人数为 $2+3+12=17$，组 $B$ 的总人数为 $5+10=15$，此时同时午休的最大人数为 $17$。
无法将部门分配得使得组 $A$ 和组 $B$ 的总人数都不超过 $16$，因此输出 $17$。

样例解释 2

可能存在多个部门人数相同的情况。

样例解释 3

例如，将第 $1,4,5$ 个部门分配到组 $A$，第 $2,3,6$ 个部门分配到组 $B$ 时，同时午休的最大人数为 $89$。

由 ChatGPT 4.1 翻译