1. 解题思路
这一题我的思路上就是一个二分的思路，先确定一个上下界，然后不断通过二分来找到最大的price不超过k的值。
因此，剩下的问题就在于对于任何一个给定的 n n n，如果确定 ∑ i = 1 n p ( i ) \sum\limits_{i=1}^{n}p(i) i=1∑np(i)的结果。
这里，我们使用的是一个迭代的结果，我们将所有数用二进制进行表示，考察 n n n的最大一位（不妨设为第 k k k位），如果这个位刚好是 x x x的整数倍且为 1 1 1，那么考察 2 k − 1 2^{k-1} 2k−1到 n n n的这段区间，其贡献的price就是 n − 2 k − 1 + 1 n-2^{k-1}+1 n−2k−1+1联合上 ∑ i = 2 k − 1 n p ( i − 2 2 k − 1 ) \sum\limits_{i=2^{k-1}}^{n} p(i - 2^{2^{k-1}}) i=2k−1∑np(i−22k−1)的部分，以及剩下的 1 1 1到 2 k − 1 − 1 2^{k-1}-1 2k−1−1的部分。
同样的，如果最高位不为 x x x的整倍数，那么直接忽略掉最高位，结果就是 ∑ i = 2 k − 1 n p ( i − 2 2 k − 1 ) \sum\limits_{i=2^{k-1}}^{n} p(i - 2^{2^{k-1}}) i=2k−1∑np(i−22k−1)的部分与剩下的 1 1 1到 2 k − 1 − 1 2^{k-1}-1 2k−1−1的部分之和。
我们将其翻译为代码语言即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def findMaximumNumber(self, k: int, x: int) -> int:
@lru_cache(None)
def dp(num):
s = bin(num)[2:]
n = len(s)
if n < x or num == 0:
return 0
a, b = num ^ (1 << (n-1)), 1<<(n-1)
if n % x == 0:
return a+1 + dp(num-b) + dp(b-1)
else:
return dp(num-b) + dp(b-1)
i, j = 0, 10**16
while j - i > 1:
m = (i+j) // 2
if dp(m) > k:
j = m
else:
i = m
return i
提交代码评测得到：耗时412ms，占用内存26MB。
