Re: [閒聊] LeetCode Weekly Contest 412
好慘 時間快到了就很緊張沒証過就開始丟 吃了一堆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
推
08/25 12:13,
1年前
, 1F
08/25 12:13, 1F
→
08/25 12:13,
1年前
, 2F
08/25 12:13, 2F
推
08/25 12:14,
1年前
, 3F
08/25 12:14, 3F
→
08/25 22:56,
1年前
, 4F
08/25 22:56, 4F
推
08/26 08:40,
1年前
, 5F
08/26 08:40, 5F
推
08/26 15:25,
1年前
, 6F
08/26 15:25, 6F