LeetCode（Heap)2335. Minimum Amount of Time to Fill Cups

今天药忘吃喽~ 2023-09-24 22:48 34阅读 0赞

# 1.问题 #

You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water.

You are given a 0-indexed integer array amount of length 3 where amount\[0\], amount\[1\], and amount\[2\] denote the number of cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.

Example 1:

> Input: amount = \[1,4,2\]  
> Output: 4  
> Explanation: One way to fill up the cups is:  
> Second 1: Fill up a cold cup and a warm cup.  
> Second 2: Fill up a warm cup and a hot cup.  
> Second 3: Fill up a warm cup and a hot cup.  
> Second 4: Fill up a warm cup.  
> It can be proven that 4 is the minimum number of seconds needed.

Example 2:

> Input: amount = \[5,4,4\]  
> Output: 7  
> Explanation: One way to fill up the cups is:  
> Second 1: Fill up a cold cup, and a hot cup.  
> Second 2: Fill up a cold cup, and a warm cup.  
> Second 3: Fill up a cold cup, and a warm cup.  
> Second 4: Fill up a warm cup, and a hot cup.  
> Second 5: Fill up a cold cup, and a hot cup.  
> Second 6: Fill up a cold cup, and a warm cup.  
> Second 7: Fill up a hot cup.

Example 3:

> Input: amount = \[5,0,0\]  
> Output: 5  
> Explanation: Every second, we fill up a cold cup.

Constraints:

*  amount.length == 3
 *  0 <= amount\[i\] <= 100

# 2. 解题思路 #

## 方法1： ##

> 1.定义result为0  
> 2.amount排序，amount\[0\]  
> 3.while循环，amount\[2\]>0&&amount\[1\]>0，值各减1，result加1;对amount排序  
> 4.while循环，如果amount\[2\]>0,amount值减1，result值加1；  
> 5.返回result

## 方法2： ##

> 必须同时装满 2 个杯子，所以如果我们的最大上限比 sum 大 2 倍，我们必须接受它，否则我们必须 2 个 2 个地移除杯子

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int fillCups(int[] amount) {
        
            int result=0;//1.定义result为0
            Arrays.sort(amount);//2.amount排序，amount[0]<amount[1]<amount[2]
            while(amount[2]>0&&amount[1]>0) {
        //3.while循环，amount[2]>0&&amount[1]>0，值各减1，result加1;对amount排序
                amount[2]--;
                amount[1]--;
                result++;
                Arrays.sort(amount);
            }
           while(amount[2]>0){
        //4.while循环，如果amount[2]>0,amount值减1，result值加1；
               amount[2]--;
               result++;
           }
            return  result;//5.返回result
        }
    }

> 解题思路基本相同

class Solution {
        
        public int fillCups(int[] amount) {
        
            int result=0;//1.定义result为0
            Arrays.sort(amount);//2.amount排序，amount[0]<amount[1]<amount[2]
            while(amount[2]>0&&amount[1]>0) {
        //3.while循环，amount[2]>0&&amount[1]>0，值各减1，result加1;对amount排序
                amount[2]--;
                amount[1]--;
                result++;
                Arrays.sort(amount);
            }
            result+=amount[2];//4.amount[2]的值大于0，其余的元素的值为0时，amount[2]的值添入到result
            return  result;//5.返回result
        }
    }

## 代码2： ##

class Solution {
        
         public int fillCups(int[] amount) {
        
            int maxCup = 0, sum = 0;
            for(int curCup: amount) {
        
                maxCup = Math.max(curCup, maxCup);
                sum += curCup;
            }
            return Math.max(maxCup, (sum + 1) / 2);
        }

> 解题思路基本相同

class Solution {
        
        public int fillCups(int[] amount) {
        
            Arrays.sort(amount);
            int high = amount[2];
            int mid = amount[1];
            int low = amount[0];
            int total=high+mid+low; 
            if(low+mid>high)  
                return total/2+total%2; //(total+1)/2
            if(low==0 && mid==0)  
              return high; 
            else  
                return high; 
    
            }
        }