题目传送门

右侧可以传送到原题位置。

题目大意

题目描述

由于 KEYENCE 总部的员工越来越多，他们决定将总部各部门分成两组，错开午休时间。

KEYENCE 总部有

N

N

N 个部门，第

i

i

i 个部门

(

1

≤

i

≤

N

)

(1\leq i\leq N)

(1≤i≤N) 的人数为

K

i

K_i

Ki​ 。

将每个部门分配到

A

A

A 组或

B

B

B 组，让每个组里面的所有人在同一时间午休，并确保

A

A

A 组和

B

B

B 组的午休时间不重叠，求同一时间午休的最大人数的最小值。

换句话说，求分配给

A

A

A 组的部门总人数和分配给

B

B

B 组的部门总人数中较大者的最小值。

数据范围

2

≤

N

≤

20

2 \leq N \leq 20

2≤N≤20。

1

≤

K

i

≤

1

0

8

1 \leq K_i \leq 10^8

1≤Ki​≤108。所有输入值均为整数。

解题思路

注意到数据范围比较小，可以考虑爆搜。

对于每个部门的人数

K

i

K_i

Ki​，由于这

K

i

K_i

Ki​ 个人只能同时在 A 组或者同时在 B 组，所以每个部门都只有两种决策：

将所有人划分在 A 组中。将所有人划分在 B 组中。

因此，我们使用 dfs 进行枚举，分别考虑第

i

i

i 个部门划分在 A 组与 B 组的情况。记

P

A

,

P

B

P_A,P_B

PA​,PB​ 分别为 A 组人数与 B 组人数，那么

a

n

s

=

max

⁡

{

a

n

s

,

min

⁡

{

P

A

,

P

B

}

}

ans = \max\{ans,\min\{P_A,P_B\}\}

ans=max{ -- -->ans,min{ PA​,PB​}}，其中

a

n

s

ans

ans 代表答案。

算法总时间复杂度为

O

(

2

n

)

\mathcal{O}(2^n)

O(2n)。

CODE：

<code>#include <bits/stdc++.h>

using namespace std;

#define int long long

int k[30], ans = 1e18, n;

inline void dfs(int step, int P_A, int P_B) { -- --> //正在遍历部门 step，A 组人数为 P_A，B 组人数为 P_B

if (step == n + 1) {

ans = min(ans, max(P_A, P_B));

return;

}

dfs(step + 1, P_A + k[step], P_B);

dfs(step + 1, P_A, P_B + k[step]);

}

signed main() {

ios::sync_with_stdio(false);

ios_base::sync_with_stdio(false);

cin.tie(0), cout.tie(0);

cin >> n;

for (int i = 1; i <= n; i++)

cin >> k[i];

dfs(1, 0, 0);

cout << ans;

return 0;

}