最火高端网站设计厂家,韩路做的网站是什么名字,深圳网站建设系统,网上商城怎么推广拔河比赛
ybtoj dfs-1-1
题目大意
给你n个数#xff0c;让你分成两堆#xff0c;使其数量相差不大于1#xff0c;问数值相差最小是多少
输入样例
1
3
55 50 100输出样例
5数据范围 1⩽T⩽501\leqslant T \leqslant 501⩽T⩽50 2⩽N⩽202\leqslant N\leqslant 202⩽N⩽…拔河比赛
ybtoj dfs-1-1
题目大意
给你n个数让你分成两堆使其数量相差不大于1问数值相差最小是多少
输入样例
1
3
55 50 100输出样例
5数据范围
1⩽T⩽501\leqslant T \leqslant 501⩽T⩽50 2⩽N⩽202\leqslant N\leqslant 202⩽N⩽20 30⩽Wi⩽12030\leqslant W_i\leqslant 12030⩽Wi⩽120
解题思路
因为N很小直接枚举每个数放在哪边即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 25
using namespace std;
int t, n, ans, a[N];
void dfs(int x, int l, int g)
{if (x n){ans min(ans, abs(g));return;}if (l (n 1) / 2) dfs(x 1, l 1, g a[x]);//放左边if (x - l (n 1) / 2) dfs(x 1, l, g - a[x]);//右边return;
}
int main()
{scanf(%d, t);while(t--){ans 120*N;scanf(%d, n);for (int i 1; i n; i)scanf(%d, a[i]);dfs(1, 0, 0);printf(%d\n, ans);}return 0;
}
