280 weeks /2171 Take out the least number of magic beans

2171. Take out the smallest number of magic beans

The question :

To give you one just An array of integers beans , Each integer represents the number of magic beans in a bag .

Please... From each bag take out Some beans （ It's fine too Don't take out ）, Make the rest Non empty In the bag （ namely At least also One Magic bean bag ） Number of magic beans equal . Once the magic beans are removed from the bag , You can't put it in any other bag .

Please return to where you need to take out the magic beans Minimum number .

Example 1：

Input ：beans = [4,1,6,5]
Output ：4
explain ：

• We never had 1 Take it out of a magic bean bag 1 A magic bean .
  The number of magic beans left in the bag is ：[4,0,6,5]
• Then we have 6 Take it out of a magic bean bag 2 A magic bean .
  The number of magic beans left in the bag is ：[4,0,4,5]
• Then we have 5 Take it out of a magic bean bag 1 A magic bean .
  The number of magic beans left in the bag is ：[4,0,4,4]
  A total of 1 + 2 + 1 = 4 A magic bean , The number of magic beans left in the non empty bag is equal .
  Nothing is better than taking out 4 A plan with fewer magic beans .

Example 2：

Input ：beans = [2,10,3,2]
Output ：7
explain ：

• We never had 2 Take it out of one of the bags of magic beans 2 A magic bean .
  The number of magic beans left in the bag is ：[0,10,3,2]
• Then we have... From another 2 Take it out of a magic bean bag 2 A magic bean .
  The number of magic beans left in the bag is ：[0,10,3,0]
• Then we have 3 Take it out of a magic bean bag 3 A magic bean .
  The number of magic beans left in the bag is ：[0,10,0,0]
  A total of 2 + 2 + 3 = 7 A magic bean , The number of magic beans left in the non empty bag is equal .
  Nothing is better than taking out 7 A plan with fewer magic beans .

Their thinking :

This problem is relatively simple if you need to use the reverse thinking method , I didn't understand until I read the answer from the boss , The idea is as follows

What the topic needs is to take out the least magic beans , If you count the numbers one by one, you can get as many as you want , Then it must be overtime ( I've tried )

Then change a thought , hold Take out the least magic beans and turn them into the most reserved magic beans , Because according to simple mathematics :

Take out the magic beans + The remaining magic beans are all magic beans . We just need to make sure that we have the most magic beans left and the least magic beans taken out ;

Then there is another problem that is how to determine how many magic beans are saved the most ?

• You can take any number first x, Magic beans smaller than this number need all to be taken away , Because... Cannot be added ;
• Those larger than this number need to take out the extra part , That is to say beans[i] - x;

Then it becomes another problem , How to determine whether the heap is to take out all the numbers or take out the redundant parts

• If you can think of sorting at this time , This problem has been completed .( Array does not have to be sorted first )
• You will find that , Start from the previous traversal , They are all bigger than him in front ( Remove the excess ), They are all smaller than him in the back ( Completely removed )

This problem is basically completed here , The general process is :

1. First calculate the total number of beans as sum, The number of heaps of beans is n
2. Sorting beans
3. Start with the first subscript , And then use sum - (n - i( The subscript )) * beans[i] You can get the remaining beans \
4. Save the least number ( Prevent overflow , All use long long);

Algorithm code

class Solution {
    
public:
    long long minimumRemoval(vector<int>& beans) 
    {
    
        sort(beans.begin(),beans.end());
        long long n = beans.size();
        long long nums = 0;
        for(auto bean : beans)
        {
    
            nums += bean; // Get the total number 
        }
        // Save results 
        long long res = nums;
        // Traverse all subscripts , Look at the smallest number saved 
        for(long long i = 0; i < n;i++)
        {
    
            long long temp = nums - (n-i) * beans[i];
            res = min(res,temp);
        }
        return  res;
    }
};

summary

If this problem doesn't change the way of thinking , It must be impossible to use violence all the time . What I wanted to do was to save the current amount of bid money , Then look at how much you need to subtract from the front . In fact, it might be too much to subtract from the total , But I didn't think . So write it down .

Source of ideas :

author ：endlesscheng
link ：https://leetcode-cn.com/problems/removing-minimum-number-of-magic-beans/solution/pai-xu-hou-yi-ci-bian-li-by-endlesscheng-36g8/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .