推 oin1104: 大師 08/25 12:13
→ Rushia: 我好崇拜你 08/25 12:13
推 argorok: 大師 08/25 12:14
→ sixB: 你真的好厲害 08/25 22:56
推 DJYOMIYAHINA: 大師... 08/26 08:40
推 dont: 大師 08/26 15:25
https://i.imgur.com/lv05W3v.png
好慘 時間快到了就很緊張沒証過就開始丟 吃了一堆WA
Q1:
因為測資很小 直接用 O(nk) 的暴力模擬就可以了
Q2/Q4:
我兩題一起寫的，首先因為 nums[i] < 1e7 所以長度 < 7
所以最多有 C(6, 2) = 15 種 swap 法
swap 兩次就是 225 種
225 * 5000 還扛的住
然後因為位數長的能 swap 成短的，反之沒辦法
所以先由大排到小
從長的開始 swap, 看能不能 swap 成右邊的即可
Q2就只swap一次
Q3:
我寫的有點複雜
總之，會存在一個最小的 r 使得最終結果
所有 nums[i] >= pow(multiplier, r)
而這可以用二分搜得到 (O(nlogk))
(檢查需要的次數是否 <= k)
之後看還剩幾次需要乘，假如還剩 p 次
找出開 log_k 的小數部分前 p 小的人
保守的話可以用分數做
這些人要多乘一次
corner case是一開始就超過 pow(multiplier, r+1) 的人要跳過
呼 好險最後有寫完
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.37.97 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724558943.A.827.html