[M数学] lc2171. 拿出最少数目的魔法豆(数学+前缀和)

发布时间:2024年01月19日

1. 题目来源

链接:2171. 拿出最少数目的魔法豆

2. 题目解析

比较简单直接的思路吧,会发现最终的转换成的数组,每个元素要么是 0,不参与结果判断,要么大家都一样。想一想这个都一样的数据有什么特殊性质。

简单想想就懂,这个都一样的数据,一定是数组中的某个元素,因为如果不是某个元素的话,其他的元素向它靠拢,肯定花费其他更多的代价。至于证明,看官解即可。

解决方案:

  • 排序,求前缀和
  • 依次计算当前元素成为这个一样元素的代价是多少
  • 代价=左侧元素的总和+右侧各个元素与当前元素的差值总和
  • 前缀和处理即可

注意下,中间计算过程会爆 int,注意转 long long 即可

还有就是官解的解答很巧妙,思路都一样,可以借鉴下。


  • 时间复杂度 O ( n ) O(n) O(n)
  • 空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        typedef long long LL;
        sort(beans.begin(), beans.end());
        LL res = 1e18;
        int n = beans.size();
        vector<int> s(n + 1, 0);
        vector<LL> beSum(n + 1);
        for (int i = 1; i <= n; i ++ ) beSum[i] += 0ll + beSum[i - 1] + beans[i - 1]; 
        for (int i = 1; i <= n; i ++ ) {
            LL cnt = 0ll + beSum[i - 1] + beSum[n] - beSum[i] - 1ll * (n - i) * beans[i - 1];
            if (res > cnt) {
                res = cnt;
            }
        }

        return res;
    }
};



作者:力扣官方题解
链接:https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/solutions/1270306/na-chu-zui-shao-shu-mu-de-mo-fa-dou-by-l-dhsl/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        int n = beans.size();
        sort(beans.begin(), beans.end());
        long long total = accumulate(beans.begin(), beans.end(), 0LL); // 豆子总数
        long long res = total; // 最少需要移除的豆子数
        for (int i = 0; i < n; i++) {
            res = min(res, total - (long long)beans[i] * (n - i));
        }
        return res;
    }
};
文章来源:https://blog.csdn.net/yl_puyu/article/details/135687030
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。