正经题解｜左右互博

题目大意

给出$n$对数字，每一组数字分别为$l_i$和$r_i$。然后你可以根据$l_i$去构建乘积总和$sum_l$ ,可以根据$r_i$去构建总和$sum_r$。

最后使得$sum_l$和$sum_r$的数值尽可能地接近，也就是绝对值差值尽可能小。

**注意:**选择的时候只能一组一组数的选择，例如选中了第$i$组数字，那么$l_i$就必须被乘进$sum_l$当中，$r_i$就必须被累加进$sum_r$当中。

解题思路

我们发现$n$最大也才10，那么我们可以去枚举出所有的组合数去求得这一道题，$C^1_{10} * C^2_{10} ... C^{10}_{10} $，时间复杂度完全够，那么问题在于如何去枚举？

当然是使用深度优先搜索去找出所有可能的组合方式。

那么在枚举出所有组合之后，不停的去取其中的差值，找到最小的一个输出即可，题目也没要求我们求出组合的搭配，所以直接输出答案即可。

演示代码

#include<bits/stdc++.h>
using namespace std;
int l[15];
int r[15];
int n;
int answer ;
void dfs(int it ,int suml,int sumr ){
	if(it > n){
		if(suml == 1 && sumr == 0){
			// 没有选任何一个计划 
			return ;
		}
		answer = min(abs(suml - sumr),answer); // 枚举所有差值比较
		return ;
	}
	
	dfs(it + 1 , suml * l[it] , sumr + r[it]);
	dfs(it + 1 , suml , sumr);
	
}

int main(){
	answer = 1e9+7;
	cin >> n ;
	for(int i = 1 ; i <= n ; i ++ )cin >> l[i] >> r[i];
	dfs(1,1,0);
	
	cout << answer << endl;
	
	return 0;
}