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) 的人要跳过
呼 好险最后有写完