class Solution {
public:
int maxCount(vector<int>& banned, int n, int maxSum) {
}
};
6304. 从一个范围内选择最多整数 I
给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：
[1, n] 。banned 中。maxSum 。请你返回按照上述规则 最多 可以选择的整数数目。
示例 1：
输入：banned = [1,6,5], n = 5, maxSum = 6 输出：2 解释：你可以选择整数 2 和 4 。 2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
示例 2：
输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1 输出：0 解释：按照上述规则无法选择任何整数。
示例 3：
输入：banned = [11], n = 7, maxSum = 50 输出：7 解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。 它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。
提示：
1 <= banned.length <= 1041 <= banned[i], n <= 1041 <= maxSum <= 109原站题解
golang 解法, 执行用时: 276 ms, 内存消耗: 6.9 MB, 提交时间: 2023-02-06 10:07:20
func min(a, b int) int {
if a < b {
return a
}
return b
}
func maxCount(banned []int, n int, maxSum int) int {
banned = append(banned, n+1)
banned = append([]int{0}, banned...)
sort.Ints(banned)
res := 0
curSum := 0
var check func(st, mid int) bool
check = func(st, mid int) bool {
return (mid * (mid + 1) /2 )-(st - 1) * st/2 + curSum <= maxSum
}
for i := 1; i< len(banned); i++ {
st := banned[i-1] + 1
ed := min(banned[i] - 1, n)
if st > n {//提前结束
return res
}
l,r := st, ed
if l > r {
continue
}
for l < r {
mid := (l+r+1)>>1
if check(st, mid){
l = mid
}else {
r = mid-1
}
}
if l <= r && (l * (l+1)/2)-(st-1)*st/2 + curSum <= maxSum {
curSum = (l * (l+1)/2)-(st-1)*st/2 + curSum
res = res + l - st + 1
}
if l != ed {
return res
}
}
return res
}
python3 解法, 执行用时: 120 ms, 内存消耗: 16.7 MB, 提交时间: 2023-02-06 10:06:28
'''
思考题: n和maxSum都很大时，怎么做？
两层二分。
由于可以贪心的优先选小数，因此枚举mx作为能枚举到的最大数。
这时判断1..mx的和是否<=k即可，具有单调性。
但是同时要去掉ban里的数据，因此可以把ban也排序求前缀和，然后查询一下ban中<=mx的部分的和。
最后答案就是mx减去ban中<=mx的数量。
总体复杂度 O(lgnlgb)
'''
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
banned = sorted(set(banned))
pre = list(accumulate(banned))
m = len(banned)
# 选最大数是x时，计算和是否超过k
def ok(x):
s = (1+x)*x//2
p = bisect_right(banned,x) - 1
s -= pre[p]
return s > maxSum
mx = bisect_left(range(n+1), True, lo=1, key=ok) - 1
return mx - bisect_right(banned, mx)
golang 解法, 执行用时: 200 ms, 内存消耗: 7.3 MB, 提交时间: 2023-02-06 10:03:01
func maxCount(banned []int, n, maxSum int) (ans int) {
has := map[int]bool{}
for _, v := range banned {
has[v] = true
}
for i := 1; i <= n && i <= maxSum; i++ {
if !has[i] {
maxSum -= i
ans++
}
}
return
}
python3 解法, 执行用时: 148 ms, 内存消耗: 16.6 MB, 提交时间: 2023-02-06 10:02:10
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
ans, s = 0, set(banned)
for i in range(1, n + 1):
if i > maxSum: break
if i not in s:
maxSum -= i
ans += 1
return ans