【每日一题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.

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

• 思路：如果存在两个杯子，那么每次装两杯；如果只存在一个杯子，那么每次装一杯。因此每次选择最大值和次大值进行装杯，尽可能每次装满两个杯子，减小最短时长。那么总时长取决于杯子的最大值$max$与剩下两个值的和$sum-max$的大小关系：

  • 杯子的最大值大于剩下两个值的和，在装该类水杯时，可以顺便把另外两个装满，那么总时长即为杯子的最大值个数。
  • 杯子的最大值小于等于剩下两个值的和，那么每次选择最大值和次大值进行装杯，那么总时长即为$\lceil sum/2\rceil$。
    • 局部最优：三种杯子的数量均匀减小，每次尽可能装满两个杯子
    • 全局最优：装满杯子的总时长最短

• 实现

  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)$