2554-从一个范围内选择最多整数 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 <= 104
• 1 <= banned[i], n <= 104
• 1 <= maxSum <= 109

Problem: 2554. 从一个范围内选择最多整数 I

[TOC]

思路

• 二分嵌套二分

解题方法

• 设 1…x的连续数字(含banned), 满足<=maxSum, x有最大的x, 且满足二分性质
• 二分查找最大的x
• 对于一个待定的x, 找到 banned 中小于等于x的所有数, 求和为:banpre
• 判定x : 如果 sum(1……x) - banpre <= maxSum, 则满足
• banned 需要去重和排序,并求前缀和, 方便寻找(banned 中小于等于x的所有数, 求和)

Code

[]

class Solution:
    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned=list(set(banned))
        banned.sort()
        banpre=[0]
        for c in banned:
            banpre.append(banpre[-1]+c)
        ss=sum(banned)
        l,r=0,n
        l=bisect_right(range(n+1), maxSum, key=lambda x:(1+x)*x//2-banpre[bisect_right(banned,x)])
        j=bisect_right(banned,l-1)
        return (l-1)-j



    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
        banned=list(set(banned))
        banned.sort()
        banpre=[0]
        for c in banned:
            banpre.append(banpre[-1]+c)
        ss=sum(banned)
        l,r=0,n
        def ck(x):
            j=bisect_right(banned,x)
            return (1+x)*x//2-banpre[j]>maxSum
        while l<=r:
            x=l+(r-l)//2
            if ck(x):
                r=x-1
            else:
                l=x+1
        j=bisect_right(banned,l-1)
        return (l-1)-j


    def maxCount_ok(self, banned: List[int], n: int, maxSum: int) -> int:
        ban = set(banned)
        ss=0
        ans=0
        for i in range(1,1+n):
            if ss+i>maxSum:
                break
            if i in ban:
                continue
            ss+=i
            ans+=1
        return ans