拔河角逐
题目链接:ybt高效进阶1-4-1
题目
要把一群人分成两组,要求人数差不超过 1,两组中每个人的值的和相差尽大概小。
求相差值最小是多少。
思路
发现人数最多只有二十个,我们考虑直接深搜。
就直接枚举每一个人在左边照旧右边,然后如果双方人数差不超过一,就算双方差值。
然后找到的所有差值算最小的,就是答案了。
代码
[code]#include#include#includeusing namespace std;int T, n, a[21], ans;void dfs(int now, int left_num, int dif) { if (now == n + 1) { if (abs(n - left_num - left_num) > 1) return ; ans = min(ans, abs(dif)); return ; } dfs(now + 1, left_num + 1, dif + a[now]);//这个人去左边 dfs(now + 1, left_num, dif - a[now]);//这个人去右边}int main() { scanf("%d", &T); for (int times = 1; times |