网站主机多少钱,dedecms 网站安全,站长统计app最新版本2023,wordpress能恢复修改前吗文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;2171. 拿出最少数目的魔法豆
2. 题目解析
比较简单直接的思路吧#xff0c;会发现最终的转换成的数组#xff0c;每个元素要么是 0#xff0c;不参与结果判断#xff0c;要么大家都一样。想一想这个都一样… 文章目录 1. 题目来源2. 题目解析 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(vectorint beans) {typedef long long LL;sort(beans.begin(), beans.end());LL res 1e18;int n beans.size();vectorint s(n 1, 0);vectorLL 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(vectorint 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;}
};
