• Leetcode 3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K

1. 解题思路

这一题我的思路上就是一个二分的思路，先确定一个上下界，然后不断通过二分来找到最大的price不超过k的值。

因此，剩下的问题就在于对于任何一个给定的$n$，如果确定$\sum _{i=1}^{n}p(i)$的结果。

这里，我们使用的是一个迭代的结果，我们将所有数用二进制进行表示，考察$n$的最大一位（不妨设为第$k$位），如果这个位刚好是$x$的整数倍且为$1$，那么考察$2^{k-1}$到$n$的这段区间，其贡献的price就是$n-2^{k-1}+1$联合上$\sum _{i=2^{k-1}}^{n}p(i-2^{2^{k-1}})$的部分，以及剩下的$1$到$2^{k-1}-1$的部分。

同样的，如果最高位不为$x$的整倍数，那么直接忽略掉最高位，结果就是$\sum _{i=2^{k-1}}^{n}p(i-2^{2^{k-1}})$的部分与剩下的$1$到$2^{k-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 0a, 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**16while j - i > 1:m = (i+j) // 2if dp(m) > k:j = melse:i = mreturn i

提交代码评测得到：耗时412ms，占用内存26MB。