Leetcode.2171 拿出最少数目的魔法豆

题目链接

Leetcode.2171 拿出最少数目的魔法豆 Rating ： 1748

题目描述

给你一个 正 整数数组

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                         <                         =                         b                         e                         a                         n                         s                         .                         l                         e                         n                         g                         t                         h                         <                         =                         1                                   0                            5                                       1 <= beans.length <= 10^5                  1<=beans.length<=105

•                                1                         <                         =                         b                         e                         a                         n                         s                         [                         i                         ]                         <                         =                         1                                   0                            5                                       1 <= beans[i] <= 10^5                  1<=beans[i]<=105

解法：排序

我们先将豆子

beans

按从小到大的顺序排序。

蓝色的就是要剩下来的豆子，白色的就是要拿走的豆子。

我们用

sum

记录所有的豆子。

蓝色部分的豆子：

    b
   
   
    e
   
   
    a
   
   
    n
   
   
    s
   
   
    [
   
   
    i
   
   
    ]
   
   
    ∗
   
   
    (
   
   
    n
   
   
    −
   
   
    i
   
   
    )
   
  
  
   beans[i] * (n - i)
  
 
beans[i]∗(n−i)

白色部分的豆子（要拿走的豆子）：

    s
   
   
    u
   
   
    m
   
   
    −
   
   
    b
   
   
    e
   
   
    a
   
   
    n
   
   
    s
   
   
    [
   
   
    i
   
   
    ]
   
   
    ∗
   
   
    (
   
   
    n
   
   
    −
   
   
    i
   
   
    )
   
  
  
   sum - beans[i] * (n - i)
  
 
sum−beans[i]∗(n−i)

所以我们只需要从

    i
   
   
    =
   
   
    0
   
  
  
   i = 0
  
 
i=0遍历到 
 
  
   
    i
   
   
    =
   
   
    n
   
   
    −
   
   
    1
   
  
  
   i = n - 1
  
 
i=n−1，遍历一遍，用一个 

ans

记录最小值即可。

时间复杂度：

    O
   
   
    (
   
   
    n
   
   
    ∗
   
   
    l
   
   
    o
   
   
    g
   
   
    n
   
   
    )
   
  
  
   O(n * logn)
  
 
O(n∗logn)

C++代码：

using LL =longlong;classSolution{public:longlongminimumRemoval(vector<int>& beans){
        LL sum =accumulate(beans.begin(),beans.end(),0LL);sort(beans.begin(),beans.end());int n = beans.size();
        LL ans =1e10;for(int i =0;i < n;i++){
            ans =min(ans , sum -(n - i)*1LL* beans[i]);}return ans;}};