C - Separated Lunch
题目链接:
C - Separated Lunch (atcoder.jp)
题目描述:
大致意思是：有n个人，让你把他们分为两个组，然后分完后的这两个组的最大值最小为多少？
数据范围：
样例输入：
5
2 3 5 10 12
样例输出：
17
题目分析：
数据范围N最大为20，典型的dfs，对每个员工进行两种情况的分析：选和不选，然后在后比较当前的sum(A组) 和 全部的人 减去 sum(B组) 的最大值和ret进行比较，取最小。
当然也可以去剪一下枝，当dfs的时候，看看当前的sum是不是已经大于ret了，大于的话直接return掉。
代码:
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int ret = 2000000010;
int n, t = 0;
int a[30];
void dfs(int len, int sum) {
if(sum > ret) {
return; // 剪
}
if(len > n) {
ret = min(ret, max(sum, t - sum));
return;
}
// 选
dfs(len + 1, sum + a[len]);
// 不选
dfs(len + 1, sum);
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i ++ ) {
cin >> a[i];
t += a[i];
}
dfs(1, 0);
cout << ret << endl;
return 0;
}
运行的结果：
原文地址：https://blog.csdn.net/m0_74304371/article/details/142719006
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！