OD C卷 - 王者荣耀游戏分组
王者荣耀游戏分组（100）
- 输入10个整数值，范围在【1,10000】，不考虑异常输入；
- 将所有整数值分为两部分，且两部分之和相差最小；
- 输出最小差值；
示例1
输入
10 9 8 7 6 5 4 3 2 1
输出
1
from collections import defaultdict # 获取的key 不存在时，调用默认的工厂函数，并返回
from bisect import bisect_left # 向一个升序排列的列表中，插入一个元素时，返回要插入的索引位置 (目标左边插入)def min_diff(alist):# 分成两部分n = len(alist) // 2pre = alist[:n]latter = alist[n:]# 所有整数总和total = sum(alist)# 左边的 字典pre_dict = defaultdict(list)# 右边的字典latter_dict = defaultdict(list)#for i in range(2**n):sum_pre = 0sum_latter = 0for j in range(n):if i & 2**j:sum_pre += pre[j]sum_latter += latter[j]cnt = bin(i).count('1')pre_dict[cnt].append(sum_pre)latter_dict[cnt].append(sum_latter)# 根据key 对列表排序for k in pre_dict:pre_dict[k].sort()latter_dict[k].sort()# 取最小差值ans = float('inf')for k in pre_dict:for sum_pre in pre_dict[k]:i = bisect_left(latter_dict[n - k], (total - 2 * sum_pre) / 2)for j in [i - 1, i, i + 1]:if 0 <= j < len(latter_dict[n - k]):ans = min(ans, abs(2 * latter_dict[n - k][j] + 2 * sum_pre - total))return ansalist = list(map(int, input().strip().split()))
print(min_diff(alist))