题解 | #牛牛的消消乐#

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

方法一：暴力方法

求解思路
对于题目给出的操作规则，我们首先对数组进行排序，使其按照递增的顺序排列。题目要求的数组和，即是原数组进行两次操作以后，减去数的总和。因此我们可以遍历每个元素，进行第一步操作以后再对其进行排序和第二部操作，最终找到能够减去的最大值，即是题目所要求的结果。

图片说明

解题代码

class Solution {
public:
    long long minimumValueAfterDispel(vector<int>& nums) {
        long long hysum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i++)
            hysum += nums[i];
        vector<int> temp = nums; // 辅助数组
        sort(nums.begin(), nums.end()); // 快排
        int max = 0;
        for(int i = 0; i < n; i++)
        {   //减去第一个数
            int delete1 = nums[i] * (n - i);
            for(int j = i; j < n; j++)
                temp[j] -= nums[i];
            sort(temp.begin(), temp.end()); // 再次排序
            for(int k = 0; k < n; k++)
            {   //减去第二个数
                int delete2 = temp[k] * (n - k);
                max = max > delete1 + delete2 ? max : delete1 + delete2; // 维护最大值
            }
            temp = nums; // 辅助数组回归原来的样子
        }
        return hysum - max; // 返回结果
    }
};

复杂度分析
时间复杂度：外层循环加上内层快排，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用辅助数组，引入额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：优化方法

求解思路
(参考复旦大学云影孤帆尽的思路)对于本题目我们可以用数学分段的优化方法来进行解题，首先我们将数组按递增顺序排列，然后任取数组中的两个数nums[i]与nums[j]，假设两次减去的数分别为a与b，那么可分为以下三种情况：
1、a=nums[j]-nums[i] b=nums[i]
2、a=nums[i] b=nums[j]-nums[i]
3、a=nums[i] b=nums[j]
然后我们可以想出分段的情况：
1、index1<i<j<n
2、i<index2<j<n
3、i<j<index3<n
然后我们对三种情况分别讨论，当[index1,i]中的数只能减nums[j]-nums[i],[i,j]中的数只能减nums[i],[j,n-1]中的数可以减去nums[j].对于其他两种情况同上述讨论。最后根据上面所述，找到三个边界值，然后用区间长度乘上减去的数即可，最后用总和减去最大值，得到结果。

图片说明

解题代码

class Solution {
public:
    long long minimumValueAfterDispel(vector<int>& nums) {
        long long hysum = 0; // 定义变量
        long long max = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end()); // 排序
        vector<long long> numl; // 将int转换成long long
        for(int i = 0; i < n; i++)
            numl.push_back((long long)nums[i]);
        for(int i = 0; i < n; i++)
        {   //求和
            hysum += numl[i];
            int index1 = i, index2 = i, index3 = i;
            for(int j = 0; j <= i; j++)
            {   //找区间边界
                while(index1 > 0 && numl[index1 - 1] >= numl[i] - numl[j])
                    index1--;
                while(index2 > i && numl[index2 - 1] >= numl[j] - numl[i])
                    index2--;
                while(index3 < n && numl[index3] < numl[j] + numl[i])
                    index3++;
                //三种情况减去的总和
                long long temp1 = (j - index1) * (numl[i] - numl[j]) + (i - j) * numl[j] + (n - i) * numl[i];
                long long temp2 = (index2 - j) * numl[j] + (i - index2) * (numl[i] - numl[j]) + (n - i) * numl[i];
                long long temp3 = (i - j) * numl[j] + (index3 - i) * numl[i] + (n - index3) * (numl[j] + numl[i]);
                max = max > temp1 ? max : temp1; // 维护最大值
                max = max > temp2 ? max : temp2;
                max = max > temp3 ? max : temp3;
            }
        }
        return hysum - max; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：引入数组numl，因此空间复杂度为 $O(N)$