AT_abc374_c.[ABC374C] Separated Lunch

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

由于 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
```
5
2 3 5 10 12
```
输出#1
```
17
```
输入#2
```
2
1 1
```
输出#2
```
1
```
输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页