力扣2171-拿出最少数目的魔法豆

拿出最少数目的魔法豆

题目链接

解题思路

横轴表示袋子，纵轴表示每个袋子中豆子的数目

• S1部分为最后袋子中剩下的豆子数目K

• S2部分是豆子数目低于K的，要全部拿走

• S3部分是豆子数目高于K的，要拿走一部分，使得豆子数目等于K

• 最后要取出的豆子数目最少，要使得S1的面积最大

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        long long int k=0;
        long long  int sum = 0;
        long long int maxs=0;
        for(int i = 0;i < beans.size(); i++){
            sum += beans[i];//计算豆子总数
        }
        sort(beans.begin(),beans.end());//排序
        for(int i = 0;i < beans.size(); i++){
            k = beans[i] * (beans.size() - i);//计算S1部分的豆子数目
            maxs = max(maxs,k);//求得S1的最大豆子数目
        }
        return sum - maxs;
    }
};