【ybt高效进阶1-4-1】拔河比赛

拔河角逐

题目链接：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