【题解】NC501 牛牛的消消乐

class Solution:
    def minimumValueAfterDispel(self, nums):
        """  NC501    牛牛的消消乐

        给定一个数组 nums，其中有 n 个非负整数。你的目的是进行两次操作，使得数组的元素之和最小。
        每次操作形如：任选一个整数 x ，将数组中所有大于等于 x 的数减去 x 。

        输入：[2,1,3]
        先选择 x = 2，则所有大于等于 2 的元素减去 2 ，变成 [0, 1, 1]。
        再选择 x = 1，则所有大于等于 1 的元素减去 1 ，变成 [0, 0, 0]。
        所以数组元素之和的最小值为 0。

        题解：
            必定要让两个数最终为0，先升序排列，假设这两个数相等，则意味着第二次选择的是0，没有意义。
            若两个数a,b(a<b)最终被选择变成0，则可以选择a, b-a; 或者b, a。
            增益是(0, b-a) 或 (b+a, ==)
            因此算法时间复杂度NNlogN
        """
        import bisect
        nums.sort()
        n = len(nums)
        res = 0
        for i in range(n):
            for j in range(i+1, n):
                ii = bisect.bisect_left(nums, nums[j]-nums[i])
                jj = bisect.bisect_left(nums, nums[j]+nums[i])
                tmp = (j-i)*nums[i]+(n-j)*nums[j]+ \
                      max((i-ii)*(nums[j]-nums[i]), (n-jj)*(nums[i])) # 第二次的增益
                res = max(res, tmp)
        return sum(nums) - res