[思维题]leetcode6006：拿出最少数目的魔法豆(medium)

题目：

题解：

思路：本题主要是思路难想，将拿出豆子数量之和的公式难想，不然双重for肯定超时。

• 1）先将数组 a 由小到大排序，然后枚举每个豆子 a[i]，a[i] 之前的所有豆子全部清 0，a[i]之后的所有豆子都减小为 a[i]，最终数组中剩余豆子的个数为 a[i]*(n-i)，而 拿走的豆子数 等于总数 sum 减去 剩余豆子数 a[i]*(n-i)，即sum-a[i]*(n-i)，最后返回拿走豆子数的最小值即可。

代码如下：

using LL = long long;
class Solution {
public:
    // 思路：排序+枚举，枚举到的元素v时，v之前的所有元素全部清0，v之后的所有元素都减小至v
    // 由于拿出豆子之和+剩余豆子之和=总豆子数，所以枚举到v时拿出豆子之和=sum-v*(n-i)
    long long minimumRemoval(vector<int>& a) {
        int n=a.size();
        sort(a.begin(),a.end());
        LL sum=accumulate(a.begin(),a.end(),0LL);
        LL res=sum;
        for(int i=0;i<n;++i){
            // a[i]之前的豆子全部清0，a[i]之后的所有豆子减小为a[i]，这样最终剩余a[i]*(n-i)个豆子，所以拿出的豆子数为sum-a[i]*(n-i)
            res=min(res,sum-1LL*a[i]*(n-i));
        }
        return res;
    }
};

最后

以上就是整齐人生为你收集整理的[思维题]leetcode6006：拿出最少数目的魔法豆(medium)的全部内容，希望文章能够帮你解决[思维题]leetcode6006：拿出最少数目的魔法豆(medium)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。