Re: [閒聊] LeetCode Biweekly Contest 138

看板Marginalman作者involution ( )時間1年前 (2024/09/01 00:00)推噓4(4推 0噓 1→)

留言5則, 4人參與討論串1/2 (看更多)

排名比想像高好多不錯 https://i.imgur.com/v8lsPjg.png

Q1: 暴力模擬 Q2: 暴力模擬 Q3: 我的解:) https://i.imgur.com/KZRk8zd.png

看到 1 <= n <= 10, 1 <= k <= 9 就想偷吃步打表因為總共只有 90 種輸入我可以提前算好即使我的演算法可能要算個好幾分鐘才算得出來也沒關係 n <= 10, 長度10以內的回文只有 <= 10^5 種我們可以遍歷他們、檢查 mod 1~9 是不是 0、再算出有多少排列組合加到相應的 ANS[n][k] 中間可以寫得很隨便反正最後求得出 90 個答案就好 :) 後來結束前突然想到萬一有人跟我一樣打表我會不會被判抄襲之類的所以補傳了求 ANS 的程式發現還是會過不會 TLE, 所以是我多慮了 Q4: 第一個觀察: power 是來浪費你注意力的可以直接求 ceil(health[i]/power)，出題人這樣很 low 再來，可以發現最後總時間是固定的，重點是殺怪順序假設 health[] 和 damage[] 已經照最後的順序排好了則受到的總傷害是 health[0] * damage[0] + (health[0] + health[1]) * damage[1] + ... 可以發現，假如存在 i，使得 health[i] * damage[i+1] > health[i+1] * damage[i] 則互換會更好，而這正好和比較 health[i] / damage[i] 等價所以可以直接照 health[i] / damage[i] 來 sort 就是答案了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.32.24 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725120020.A.931.html

推

argorok

09/01 00:01, 1年前 , 1^F

09/01 00:01, 1^F

推

oin1104

09/01 00:07, 1年前 , 2^F

09/01 00:07, 2^F

推

Che31128

09/01 00:07, 1年前 , 3^F

09/01 00:07, 3^F