牛牛的消消乐

题意

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

题解

我们不妨假设第一次选择的 ，第二次选择的 。那么就会存在一些数被减去了 ，一些数被减去了 ，一些数被减去了 ，一些数被减去了 。我们假设 ，所以这五个数也形成了四个区间。有 。我们记 ，表示对于这个值域的区间，有多少个元素落在其中。那么我们能够消除的方块数量就是：

注意到 是阶跃函数，即当没有任何一列方块的高度等于 或 的时候，使 做小范围加减， 的值是不会变化的。所以最大值一定再阶跃函数的端点取到，所以我们只需要枚举出现过的值就好了。

注意：

• 确定两个就可以确定另外一个，所以只需要枚举两个值，且 不一定都出现在 nums 中，例如数据二中 nums = [2, 3, 3, 4, 4]。此时选取 a = 3, b = 1 是最佳答案。
• 我们需要分三种情况讨论，分别枚举 a 不出现在 nums 中，b 不出现在 nums 中，a + b 不出现在nums中的情况。
• a + b 可能会爆掉 int。

根据以上的分析可以得出以下解法：

解法一

直接在 的范围内枚举 a，b，再遍历每一个元素，计算最终剩下的值之和。如果设数组元素的最大值为 , 数组长度为 ，时间复杂度是 ，需要额外 的空间，不可以通过本题。

解法二

在解法一的基础上，优化掉枚举 a, b 之后对于每个数组元素的遍历，可以对数组采取排序的方法。在有序的数组上进行二分或则双指针操作，将时间复杂度降到 或者 ，不可以通过此题。

解法三

继续优化改进，猜想 a，b 一定都是出现在数组中的元素，将 的枚举降为 ，总体时间复杂度将为 或者 。但是此时的正确性有问题。如下列数据

[2, 3, 3, 4, 4]

若只枚举数组中出现的数作为 a, b，是不可能取到最优解 1 的。

所以这个做法复杂度正确，但是思路错误，不可以通过此题。

解法四

如果意识到 a + b 也可能是出现在数组中的元素，那么设 c = a+b 。进行三次枚举，分别枚举 (a, b), (a, c)，(b, c)，并假设他们分别在数组的元素中出现过，然后三次计算结果取最小值。这样就可以通过此题了。时间复杂度 ，空间复杂度 。

代码

class Solution {
public:
    /**
     * 返回两次操作后，数组元素之和的最小值
     * @param nums int整型vector 这你你需要操作的数组
     * @return long长整型无类型
     */
    long long minimumValueAfterDispel(vector<int> nums)
    {
        // write code here
        using ll = long long;
        sort(nums.begin(), nums.end());
        long long sum = 0, dec = 0;
        for (auto num : nums) sum += num;
        for (int a = 0; a < nums.size(); a++) {
            int ab = a;
            for (int b = 0; b <= a; b++) {
                while (ab < nums.size() && (ll)nums[ab] < (ll)nums[a] + nums[b]) ab++;
                ll tmp = (ll)nums[b] * (a - b)
                       + (ll)nums[a] * (ab - a)
                       + ((ll)nums[a] + nums[b]) * (nums.size() - ab);
                dec = max(dec, tmp);
            }
        }

        for (int a = 0; a < nums.size(); a++) {
            int b = 0;
            for (int ab = a; ab < nums.size(); ab++) {
                while (b < a && nums[b] < nums[ab] - nums[a]) b++;
                ll tmp = ((ll)nums[ab] - nums[a]) * (a - b)
                       + (ll)nums[a] * (ab - a)
                       + (ll)nums[ab] * (nums.size() - ab);
                dec = max(dec, tmp);
            }
        }

        for (int b = 0; b < nums.size(); b++) {
            int a = b;
            for (int ab = b; ab < nums.size(); ab++) {
                while (a < ab && nums[a] < nums[ab] - nums[b]) a++;
                ll tmp = (ll)nums[b] * (a - b)
                       + ((ll)nums[ab] - nums[b]) * (ab - a)
                       + (ll)nums[ab] * (nums.size() - ab);
                dec = max(dec, tmp);
            }
        }
        return sum - dec;
    }
};