【每日一题Day115】LC2335装满杯子需要的最短总时长 | 贪心

装满杯子需要的最短总时长【LC2335】

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.

什么时候天晴呀（又在草稿里没发出来）

• 思路：如果存在两个杯子，那么每次装两杯；如果只存在一个杯子，那么每次装一杯。因此每次选择最大值和次大值进行装杯，尽可能每次装满两个杯子，减小最短时长。那么总时长取决于杯子的最大值m a x 与剩下两个值的和s u m − 的大小关系：
• 杯子的最大值大于剩下两个值的和，在装该类水杯时，可以顺便把另外两个装满，那么总时长即为杯子的最大值个数。杯子的最大值小于等于剩下两个值的和，那么每次选择最大值和次大值进行装杯，那么总时长即为⌈ s u m / 2 ⌉ 。

• 局部最优：三种杯子的数量均匀减小，每次尽可能装满两个杯子
• 全局最优：装满杯子的总时长最短

• 实现
  

class Solution {
    public int fillCups(int[] amount) {
        int max = 0;
        int sum = 0;
        for (int num : amount){
            sum += num;
            max = Math.max(num, max);
        }
        if (max > sum - max) {
            return max;
        }else{
            return sum / 2 + sum % 2;
        }
    }
}

复杂度

时间复杂度：O ( 1 )

空间复杂度：O ( 1 )