洛谷 AT_abc374_c [ABC374C] Separated Lunch 题解

题目大意

KEYENCE 总部有 $N$ 个部门，第 $i$ 个部门有 $K_i$ 个人。

现在要把所有部门分为 AB 两组，求这两组中人数多的那一组的人数最少为多少。

题目分析

设这些部门共有 $x$ 个人，则较多的组的人数肯定大于等于 $\lceil \frac{x}{2}\rceil$。

由于这两个组哪一个大对答案没影响，所以可以直接枚举每一个部门是否加入 A 组，当人数超过 $\lceil \frac{x}{2}\rceil$ 时更新答案即可。

Code

#include <iostream>
using namespace std;
int n, k[20], sum, ans = 2147483647;
void dfs(int x, int y) {//x 为当前判断的部门编号，y 为人数总和if (y >= sum) {ans = min(ans, y);//更新答案return;}if (x >= n) return;dfs(x + 1, y + k[x]);//加入dfs(x + 1, y);//不加入
}
signed main() {ios::sync_with_stdio(false), cin.tie(), cout.tie();cin >> n;for (int i = 0; i < n; ++i) cin >> k[i], sum += k[i];//sum 求总和sum = (sum + 1) / 2;//除以 2（向上取整）dfs(0, 0);cout << ans;return 0;
}