LeetCode__ 301 weekly games 6112. Minimum total time required to fill the cup___ Greedy two methods

6112. The minimum total time required to fill the cup

There is a water dispenser , Cold water can be prepared 、 Warm and hot water . Every second , Can be filled 2 A cup of Different Type of water or 1 Cup any type of water .

I'll give you a subscript from 0 Start 、 The length is 3 Array of integers for amount , among amount[0]、amount[1] and amount[2] Respectively means that it needs to be filled with cold water 、 Number of cups of warm and hot water . Return to fill all cups least Number of seconds .

Example 1：

Input ：amount = [1,4,2]
Output ：4
explain ： Here is a scheme ：
The first 1 second ： Fill a cup of cold water and a cup of warm water .
The first 2 second ： Fill a cup of warm water and a cup of hot water .
The first 3 second ： Fill a cup of warm water and a cup of hot water .
The first 4 second ： Fill a glass of warm water .
It can be proved that at least 4 Seconds to fill all the cups .

Example 2：

Input ：amount = [5,4,4]
Output ：7
explain ： Here is a scheme ：
The first 1 second ： Fill a cup of cold water and a cup of hot water .
The first 2 second ： Fill a cup of cold water and a cup of warm water .
The first 3 second ： Fill a cup of cold water and a cup of warm water .
The first 4 second ： Fill a cup of warm water and a cup of hot water .
The first 5 second ： Fill a cup of cold water and a cup of hot water .
The first 6 second ： Fill a cup of cold water and a cup of warm water .
The first 7 second ： Fill a glass of hot water .

Example 3：

Input ：amount = [5,0,0]
Output ：5
explain ： Fill a glass of cold water every second .

Tips ：

• amount.length == 3
• 0 <= amount[i] <= 100

Solution1:

At first, I thought there was a difference between cold water and warm water , So keep it cold 、 temperature 、 heat The order of the three states , Maintenance amount The meaning of the three positions of the array remains unchanged . So every time according to greed , First take the smallest and the largest and combine them in pairs , Until the two kinds of water have been taken away , Take the rest one by one ;

Be careful ：

Try to judge the legality first and then calculate , Otherwise, the operation needs more if Judge whether you crossed the line

Code1:

class Solution {
    
    public int fillCups(int[] amount) {
    
        int len = amount.length;
        int time = 0;
        while(true){
    
            int zero = 0;
            for(int i=0;i<len;i++){
    
                if(amount[i] == 0)
                    zero++;
            }
            if(zero == 2 || zero == 3){
    
                break;
            }
            //  Try to judge the legality first and then calculate , Otherwise, the operation needs more if Judge whether you crossed the line 
            
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i=0;i<len;i++){
    
                if(amount[i] == 0)
                    continue;
                max = Math.max(max,amount[i]);
                min = Math.min(min,amount[i]);
            }
            
            int flag = 0;
            for(int i=0;i<len;i++){
    
                if(amount[i] == 0)
                    continue;
                if(flag == 0){
    
                    if(amount[i] == max){
    
                        flag = 1;
                        amount[i]--;
                    }
                    else if(amount[i] == min){
    
                        flag = 2;
                        amount[i]--;
                    }
                }
                else if(flag == 1){
    
                    if(amount[i] == min){
    
                        amount[i]--;
                        break;
                    }
                }
                else{
    
                    if(amount[i] == max){
    
                        amount[i]--;
                        break;
                    }  
                }
            }
            time++;
        }
        
        //  The remaining single ones do not need to be traversed , Because the value represents how many times 
        return time + amount[0] + amount[1] + amount[2];
    }
}

Solution2:

• Later, it was found that there was no need to maintain the order of the three kinds of water , Because as long as you take two different kinds of water each time , So it doesn't matter what kind of water they are , Just know that the three of them are different types , So we can amount Array to modify , Sort directly each time , Take the first two largest .

It should be noted that , Because we can operate on two kinds of water every time , It is also possible to operate on a kind of water , So we don't need to separate this operation into two stages , Can be directly together , That is, as long as it complies with the operation of two kinds of water, it will operate on two kinds of water , If it doesn't meet the requirements, just operate on a kind of water . And if the amount Turn into [0,0,0] Cannot operate , We can directly judge whether the maximum value obtained after sorting is 0 To determine whether the array is all 0;

Code2:

class Solution {
    
    public int fillCups(int[] amount) {
    
        int len = amount.length;
        int res = 0;
        while(true){
    
            Arrays.sort(amount);
            boolean flag = false;
            if(amount[2] != 0){
    
                amount[2]--;
                flag = true;
            }
            
            if(amount[1] != 0){
    
                amount[1]--;
            }
            
            if(!flag){
    
                break;
            }
            //  It needs to be the real subtraction from the front , frequency res To add one , So judge first 
            res++;
        }
        
        return res;
    }
}