第 255 场周赛 5853. 从子集的和还原数组#
这个题在比赛的时候没有想出来,记录一下当时的思路
观察一下样例,比较容易看出来的是,sums里面的最大值肯定是所有正整数的和(如果没有正整数,最大值为空集的和 0),最小值是所有负整数的和(如果没有负整数,最小值为空集的和 0)
题目里给的 n 比较小,2^n 也才 3w+,考虑暴力的做法
怎么样求出数组里的数呢,有一个比较简单的想法:对 sums 数组进行排序,如果最小值 sums[0] 为 0,则其中有一个数肯定是 sums[1];如果最大值 sum[len-1] 为 0,则其中有一个数肯定是 sums[len-2];如果最小值 < 0,最大值 > 0,则有一