Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者pandix (麵包屌)時間3年前 (2022/10/29 14:55)推噓3(3推 0噓 2→)

留言5則, 5人參與討論串72/719 (看更多)

2136. Earliest Possible Day of Full Bloom 給你 n 朵花和他們需要的種植時間/生長時間，問你最短要幾天才能讓他們全部綻放種植準備可以不連續，一天只能執行一朵花的種植準備當一朵花的準備完成後就會自己生長直到生長時間後綻放 Example 1: Input: plantTime = [1,4,3], growTime = [2,3,1] Output: 9 Day 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 1 P G G G(綻放) 2 P P P P G G G G(綻放) 3 P P P G G(綻放) 思路: 1.看測資範圍感覺像 greedy 或二分搜，雖然種植準備沒有要求連續不過連續會比較好連續代表同樣的時間內有人會被提早完成所以最後的答案應該是依某種順序完成 n 朵花的準備然後再算出他們的時間 2.一個簡單的策略就是生長時間最長的我們就先完成他道理很簡單假如最後一朵花種植完成我們的總時間至少要加上他的生長時間所以這個生長時間越短應該是越有優勢也就是說那些生長時間長的要先做完因此就對 growTime sorting 然後大的先種最後再 iterate 一次看每朵花前面的總種植時間+自己的生長時間這個最大值發生在哪 3.假設最佳解的種植順序中出現了*相鄰並且先種生長時間短的再種生長時間長的組合這樣我們就有兩朵花的種植時間 p1, p2 和生長時間 g1, g2 並且 g1 <= g2 如果先種 1: p1 g1 ------- ----- p2 g2 ------- ------ 可以算出時間 = p1 + max(g1, p2+g2) = p1 + p2 + max(g2, g1-p2) 如果先種 2: p2 g2 ------- ----- p1 g1 ------- ------ 可以算出時間 = p2 + max(g2, p1+g1) = p2 + p1 + max(g1, g2-p1) 又前面提到 g1 <= g2 因此先種1的情況會是 p1+p2+g2 這時候把兩種狀況的最後一項拿來比較也就是 g2 和 max(g1, g2-p1) 可以發現 g2 >= g1 並且 g2 > g2-p1 也就是說先種2 不會比先種1更差如果最佳解存在這種組合那交換後的結果不會差於最佳解如此不停交換後的結果也就是 growTime 呈遞減數列(可以想像成bubble sort) 也不會差於最佳解這樣 greedy 就成立了 4.Python code: class Solution: def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int: n = len(plantTime) time = sorted(zip(growTime, plantTime), reverse=True) totalplant = res = 0 for grow, plant in time: totalplant += plant res = max(res, totalplant+grow) return res -- 蛤? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.176 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667026509.A.4AC.html

推

Jaka

10/29 14:55, 3年前 , 1^F

10/29 14:55, 1^F

→

pandafatfat

10/29 14:55, 3年前 , 2^F

10/29 14:55, 2^F

推

Rushia

10/29 14:55, 3年前 , 3^F

10/29 14:55, 3^F