题解 | #牛牛的消消乐#

牛牛的消消乐

http://www.nowcoder.com/practice/9deb03b935ec4fd288a8ee5d20364581

思路：

题目的主要信息：

对一个数组，每次选1个元素进行操作，两次操作后使数组和最小
操作为：任选一个元素x，将数组中所有大于等于x的数减去x

方法一：暴力法
具体做法：
首先对数组进行排序，使之成为递增顺序。求一个数组的和sum，然后就是找到sum要减去的最大值。这个最大值就是进行两次操作的时候要减去的数的总和。
因为数组是递增次数，因此我们如果要减去的元素是 $nums[i]$ ，那么从下标 $i$ 到 $n-1$ 全部都可以减去，减去的部分就是 $nums[i] * (n - i)$ ，因此我们可以遍历每个元素，减去1个之后，再对其排序再遍历减去第二个元素，找到能够减去的最大值。
最后sum减去最大值就是所求结果。

class Solution {
public:
    long long minimumValueAfterDispel(vector<int>& nums) {
        long long sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i++)
            sum += 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 j = 0; j < n; j++){
                int delete2 = temp[j] * (n - j);  //减去第二个数
                max = max > delete1 + delete2 ? max : delete1 + delete2; //维护最大值
            }
            temp = nums; //辅助数组回归原来的样子
        }
        return sum - max;
    }
};

复杂度分析：

时间复杂度： $O(n^2log_2n)$ ，第一个排序为 $O(nlog_2n)$ ，与后面的比较起来可忽略；第一层遍历是 $O(n)$ ，循环里面有三个 $O(n)$ （分别是减去第一个数、找到减去第二个数的最大值、回归辅助数组），循环里面还有一个sort排序 $O(nlog_2n)$ ，故最终的结果是 $O(nlog_2n+n*(n+n+n+nlog_2n))=O(n^2log_2n)$
空间复杂度： $O(n)$ ，辅助数组temp

方法二：数学分段法
具体做法：
首先将数组排成增序。
遍历的数组中的任意两个数 $nums[i]$ 与 $nums[j]$ ，我们可以假设两次减去的数分别为 $a$ 与 $b(a<b)$ ，那么可以分为三种情况：

$a=nums[j]-nums[i]$ $b=nums[i]$
$a=nums[i]$ $b=nums[j]-nums[i]$
$a=nums[i]$ $b=nums[j]$

与之对应的定义域函数分段：

$index1 < i < j < n$
$i < index2 < j < n$
$i < j < index3 < n$

对于情况1： $[index1,i]$ 中的数只能减 $nums[j]-nums[i]$ , $[i,j]$ 中的数只能减 $nums[i]$ , $[j,n-1]$ 中的数可以减去 $a+b$ ，即 $nums[j]$
对于情况2： $[i,index2]$ 中的数只能减 $nums[i]$ , $[index2,j]$ 之间的数只能减 $nums[j]-nums[i]$ , $[j,n-1]$ 中的数可以才减 $a+b$ ，即 $nums[j]$
对于情况3： $[i,j]$ 中的数只能减 $nums[i]$ , $[j,index3]$ 中的数只能减 $nums[j]$ , $[index3,n-1]$ 中的数才可以减 $a+b$ ，即 $nums[j]+nums[i]$

图片说明
因此我们遍历两层数组，找到三个边界值index1 index2 index3，然后用区间长度乘上减去的数即可，寻炸这三种情况的最大值，用总和减去最大值即可得到结果。
（以下代码因为遍历顺序问题，i与j与上述相反）

class Solution {
public:
    long long minimumValueAfterDispel(vector<int>& nums) {
        long long sum = 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++){
            sum += 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 sum - max;
    }
};

复杂度分析：