题目传送门
右侧可以传送到原题位置。
题目大意
题目描述
由于 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：
#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;
}