发表于 2024.05.14

• 本质思路就是遍历所有的任务，累加完成每一任务的最少轮数就行。而对于如果计算单个任务完成的最少轮数，一开始使用了动态规划，即完成i个相同任务的时间未MinRounds[i] = (MinRounds[i - 3], MinRounds[i - 2]) + 1；后面发现使用贪心即可：如果任务个数i满足被3整除，则最少轮数为i // 3；若i % 3 == 2，则先完成两个，然后再三个三个完成，即最少轮数为i // 3 + 1；若i % 3 == 1，则先完成两次-2，再三个三个完成，即2 + (i - 4) // 3 = i // 3 + 1。

  一开始使用动态规划的做法：

  class Solution:
      def minimumRounds(self, tasks: List[int]) -> int:
          cnt_map = {}
          max_cnt = 0
          for task in tasks:
              cnt_map[task] = cnt_map.get(task, 0) + 1
              max_cnt = max(max_cnt, cnt_map[task])
  
          dp = [0] * (max_cnt + 1)
          dp[0], dp[1] = 0, math.inf
          for i in range(2, max_cnt + 1):
              dp[i] = dp[i - 2]
              if i - 3 >= 0:
                  dp[i] = min(dp[i - 2], dp[i - 3])
              dp[i] += 1
          ans = 0
          for cnt in cnt_map.values():
              if dp[cnt] == math.inf:
                  return -1
              ans += dp[cnt]
          return ans

  改进为贪心的做法：

  class Solution:
      def minimumRounds(self, tasks: List[int]) -> int:
          cnt_map = {}
          for task in tasks:
              cnt_map[task] = cnt_map.get(task, 0) + 1
          
          ans = 0
          for cnt in cnt_map.values():
              if cnt == 1:
                  return -1
              
              if cnt % 3 == 0:
                  ans += cnt // 3
              else:
                  ans += 1 + (cnt // 3)
          return ans

• LC 题目链接