leetcode 6006. 拿出最少数目的魔法豆

//排序后枚举每个位置k，表示1-k-1全部为0，剩余都为beans[k-1];

//这样对每个位置k都有结论∑sum[i]-(n-k+1)*beans[k-1]；取个min就行

 1 class Solution {
 2 public:
 3     long long minimumRemoval(vector<int>& beans) {
 4         int n=beans.size();
 5         sort(beans.begin(),beans.end());
 6         long long sum[n+1];
 7         sum[0]=0;
 8         long long mx=0;
 9         for(int i=1;i<=n;i++)sum[i]=sum[i-1]+beans[i-1];
10         for(int i=1;i<=n;i++)
11         mx=max(mx,1ll*(n-i+1)*beans[i-1]);
12         
13         return sum[n]-mx;
14     }
15 };