网站开发技术可行性,辽宁省工程建设信息网官网,wordpress 生成海报,苏州做网站知识的分享题目大意
KEYENCE 总部有 N N N 个部门#xff0c;第 i i i 个部门有 K i K_i Ki 个人。
现在要把所有部门分为 AB 两组#xff0c;求这两组中人数多的那一组的人数最少为多少。
题目分析
设这些部门共有 x x x 个人#xff0c;则较多的组的人数肯定大于等于 ⌈ …题目大意
KEYENCE 总部有 N N N 个部门第 i i i 个部门有 K i K_i Ki 个人。
现在要把所有部门分为 AB 两组求这两组中人数多的那一组的人数最少为多少。
题目分析
设这些部门共有 x x x 个人则较多的组的人数肯定大于等于 ⌈ x 2 ⌉ \lceil\frac{x}{2}\rceil ⌈2x⌉。
由于这两个组哪一个大对答案没影响所以可以直接枚举每一个部门是否加入 A 组当人数超过 ⌈ x 2 ⌉ \lceil\frac{x}{2}\rceil ⌈2x⌉ 时更新答案即可。
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;
}
