题目大意
给出nnn对数字,每一组数字分别为lil_ili 和rir_iri 。然后你可以根据lil_ili 去构建乘积总和sumlsum_lsuml ,可以根据rir_iri 去构建总和sumrsum_rsumr 。
最后使得sumlsum_lsuml 和sumrsum_rsumr 的数值尽可能地接近,也就是绝对值差值尽可能小。
**注意:**选择的时候只能一组一组数的选择,例如选中了第iii组数字,那么lil_ili 就必须被乘进sumlsum_lsuml 当中,rir_iri 就必须被累加进sumrsum_rsumr 当中。
解题思路
我们发现nnn最大也才10,那么我们可以去枚举出所有的组合数去求得这一道题,$C^1_{10} * C^2_{10} ... C^{10}_{10} $,时间复杂度完全够,那么问题在于如何去枚举?
当然是使用深度优先搜索去找出所有可能的组合方式。
那么在枚举出所有组合之后,不停的去取其中的差值,找到最小的一个输出即可,题目也没要求我们求出组合的搭配,所以直接输出答案即可。
演示代码