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