比较简单直接的思路吧,会发现最终的转换成的数组,每个元素要么是 0,不参与结果判断,要么大家都一样。想一想这个都一样的数据有什么特殊性质。
简单想想就懂,这个都一样的数据,一定是数组中的某个元素,因为如果不是某个元素的话,其他的元素向它靠拢,肯定花费其他更多的代价。至于证明,看官解即可。
解决方案:
注意下,中间计算过程会爆 int,注意转 long long 即可
还有就是官解的解答很巧妙,思路都一样,可以借鉴下。
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;
}
};