LC.P2171[拿出最少数目的魔法豆]

方法一：排序+枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans);
        long sum = 0;
        for (int x : beans) sum += x;
        long ans = sum;
        int n = beans.length;
        for (int i = 0; i < n; ++i) {
            ans = Math.min(ans, sum - (long) beans[i] * (n - i));
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(logn)$