2702：使数字变为非正数的最小操作次数（★★）

力扣第 2702 题

题目

给定一个 下标从0开始 的整数数组 nums，以及两个整数 x 和 y。在每一次操作中，你需要选择一个满足条件 0 <= i < nums.length 的下标 i ，并执行以下操作：

• 将 nums[i] 减去 x。
• 将除了下标为 i 的位置外，其他位置的值都减去 y。

返回使得 nums 中的所有整数都 小于等于零 所需的最小操作次数。

示例 1：

输入：nums = [3,4,1,7,6], x = 4, y = 2
输出：3
解释：你需要进行三次操作。其中一种最优操作序列如下：
操作 1: 选择 i = 3。 然后, nums = [1,2,-1,3,4].
操作 2: 选择 i = 3。 然后, nums = [-1,0,-3,-1,2].
操作 3: 选择 i = 4。 然后, nums = [-3,-2,-5,-3,-2].
现在，nums 中的所有数字都是非正数。因此，返回 3。

示例 2：

输入：nums = [1,2,1], x = 2, y = 1
输出：1
解释：我们可以在 i = 1 处执行一次操作，得到 nums = [0,0,0]。所有正数都被移除，因此返回 1。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= y < x <= 109

分析

二分 check 即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minOperations(self, nums: List[int], x: int, y: int) -> int:
        def check(k):
            res = 0
            for a in nums:
                if a>k*y:
                    res += (a-k*y-1)//(x-y)+1
            return res<=k
        ma = sum(a//x+1 for a in nums)
        return bisect_left(range(ma),True,key=check)

615 ms