「暴力」拿出最少数目的魔法豆(力扣第2171题)

本题为1月18日力扣每日一题

题目来源:力扣第2171题

题目tag:数位dp 动态规划

题面

题目描述

给定一个正整数数组beans,其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中拿出一些豆子(也可以不拿出),使得剩下的非空袋子中(即至少还有一颗魔法豆的袋子)魔法豆的数目相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的最少数目。

示例

示例 1

输入:

beans = [4,1,6,5]

输出:

4

解释:

  • 我们从有1个魔法豆的袋子中拿出1颗魔法豆。
    剩下袋子中魔法豆的数目为:[4,0,6,5]
  • 然后我们从有6个魔法豆的袋子中拿出2个魔法豆。
    剩下袋子中魔法豆的数目为:[4,0,4,5]
  • 然后我们从有5个魔法豆的袋子中拿出1个魔法豆。
    剩下袋子中魔法豆的数目为:[4,0,4,4]

总共拿出了 \(1 + 2 + 1 = 4\) 个魔法豆,剩下非空袋子中魔法豆的数目相等。

没有比取出4个魔法豆更少的方案。

示例 2

输入:

beans = [2,10,3,2]

输出:

7

解释:

  • 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
    剩下袋子中魔法豆的数目为:[0,10,3,2]
  • 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
    剩下袋子中魔法豆的数目为:[0,10,3,0]
  • 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
    剩下袋子中魔法豆的数目为:[0,10,0,0]

总共拿出了 2 + 2 + 3 = 7 个魔法豆,剩下非空袋子中魔法豆的数目相等。

没有比取出 7 个魔法豆更少的方案。

提示

\(1 \leq beans.length \leq 10^5\)
\(1 \leq beans[i] \leq 10^5\)


思路分析

以前做过一道要求所有数相等求最少步数的题目,当时这题既可以增加也可以减少,是在转化问题后借助对顶堆这种数据结构来实现的,因此这题我的第一反应也是用同样的方式转化问题然后尝试解决,发现并没有什么用。

于是我开始思考是否能用其他数据结构,思考了许久也没有什么答案。然后我想能不能找到一种使得结果单调的方式,然后使用二分来解决问题。经过较长时间思考后我终于发现,这题只要直接暴力即可。

首先显然,最终统一化成的数(除了0)一定是给定数组中的某一个元素,这个性质在此处不做证明。那么,我只需要枚举每一个元素,然后分别计算需要取出的糖果的数目即可。这个计算很简单,大于选定元素的数,取出他们的差值即可;小于选定元素的数,由于不能加糖果,所以全部取出。但是这样是一个平方级别的复杂度,显然会超时,有没有办法优化呢?

由于我是从二分的角度入手思考的,所以我直接找到了解决的办法。对于正常的思考逻辑,我想可能可以这样理解:

  • 之所以直接枚举会使得复杂度达到平方,是因为在每次枚举一个数之后,我们一直在重复遍历整个数组来计算差值
  • 能否采取一种方式可以利用前一次计算的结果来得出当前的结果,省略掉重复的过程?
  • 因为这个结果实际上是差值,显然我每次调高或减小基准值时,每个大于等于新基准值的数所贡献的差值变化就是基准值的变化,因为 $(a - b) - (a - c) = c - b $ ;小于原本基准值的数的贡献不会改变,因为他们已经被减到0了;在两者之间的数(前闭后开)的贡献的变化就是原本的基准值,因为 \(a - (a - b) = b\)
  • 所以问题变成给定数组中的一个值,我能否快速知道数组中几个数比他小,几个数比他大。非常容易,我给数组排个序就好了。而且在排序后按顺序进行遍历时,你会发现上述所说的“在两者之间的数“其实只有前一次取的那个数,所以只需要直接将其从贡献中减掉即可

有了上面这个优化思路后,本题的做法非常容易。首先对数组进行一次排序,然后从小到大遍历整个数组,依次把每个数当成当前的基准值。每次的取出糖果数,就是上一次的取出糖果数,减去上一个基准值(介于两个基准值之间的数的贡献变化),然后加上当前元素及以后的元素个数乘上两次基准值的差(大于等于当前基准值的数的贡献变化)即可。这里注意计算第一个元素为基准值时的情况中,由于没有上一次取出糖果数,无法递推,因此只能直接遍历整个数组,依次计算差值。

注意此题的中间结果可能很大,会超过int的上限,需要开long long十年oi一场空,不开long long见祖宗。

参考代码

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        sort(beans.begin(),beans.end());

        // 第一个元素没有前一次的结果,直接计算
        long long cnt = 0;
        for(auto w : beans) {
            cnt += w - beans[0];
        }

        long long res = cnt;
        // 依次枚举每一项
        for(int i = 1;i < beans.size();i++){
            // 前一项变成0,贡献变化为前一项
            cnt += beans[i - 1];
            // 后面每项贡献变化为两次基准值的差值
            cnt -= 1LL * (beans[i] - beans[i - 1]) * (beans.size() - i);
            res = min(res,cnt);
        }

        return res;
    }
};

"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德

热门相关:诛明   霍先生结婚吧   霍先生结婚吧   锦衣当国   锦绣医妃之庶女凰途