Leetcode 2244 - Minimum Rounds to Complete All Tasks

題目

Problem#

給你一個整數陣列 N 其中 N[i] 代表工作的困難度，每回合可以完成兩個或三個同等級的工作，問你最少要幾回合?

• 測資範圍:
  • $1 \le N.size() \le 10^5$
  • $1 \le N[i] \le 10^9$

想法#

先 sort 一次，接著數相同的數字個數存成陣列，直接模擬完成工作 $O(nm)$ (m=N[i])

觀察:

1 -> -1
2 ->  1 (2)
3 ->  1 (3)
4 ->  2 (2+2)
5 ->  2 (3+2)
6 ->  2 (3+3)
7 ->  3 (3+2+2)
8 ->  3 (3+3+2)
9 ->  3 (3+3+3)
...

可以得出規則: ans = ans + (i / 3) + (i % 3 != 0) 掃一次就得出答案 $O(n)$

• 時間複雜度: $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

賞析#

https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/solutions/2996569/ruby-solution-3-lines/?orderBy=most_votes

心得#

貪心規則感覺明明自己可以想到，太快看提示了，之後要像打比賽那樣先給自己時間練習QQ (下班就好懶QQ)