1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/minimum-operations-to-make-numbers-non-positive/description/

2.解题方法

2.1.解题思路

二分查找

2.2.解题步骤

第一步，构建二分检查函数，检查在k个步骤是否能够完成题目给定的任务

1.1.枚举nums中每一个数字num，全局最多减去k个x，那么可以从每个num中减去k*y个贡献，剩余k个(x-y)的减法进行分配，观察能否够分配；所以如果k*y>=num，那么num不用分配(x-y)，反之从k中分配math.ceil((num-k*y)/(x-y))个(x-y)，如果够分配则枚举下一个num，否则k个步骤不够分配，返回False

第二步，二分主体。红蓝染色：红色区域代表不能完成任务的k值，蓝色区域代表能够完成任务的k值；左开右开；left始终指向红色区域，right始终指向蓝色区域；最终的right即为题解。

3.解题代码

Python代码

import math

class Solution:
    def minOperations(self, nums: List[int], x: int, y: int) -> int:
        # 思路：二分查找
        # 第一步，构建二分检查函数，检查在k个步骤是否能够完成题目给定的任务
        def check(k:int) -> bool:
            # 1.1.枚举nums中每一个数字num，全局最多减去k个x，那么可以从每个num中减去k*y个贡献，剩余k个(x-y)的减法进行分配，观察能否够分配；所以如果k*y>=num，那么num不用分配(x-y)，反之从k中分配math.ceil((num-k*y)/(x-y))个(x-y)，如果够分配则枚举下一个num，否则k个步骤不够分配，返回False
            remains = k
            for num in nums:
                if k * y >= num:
                    continue
                a = math.ceil((num - k * y) / (x - y))
                if remains < a:
                    return False
                remains -= a
            return True
        # 第二步，二分主体。红蓝染色：红色区域代表不能完成任务的k值，蓝色区域代表能够完成任务的k值；左开右开；left始终指向红色区域，right始终指向蓝色区域；最终的right即为题解
        left, right = 0, math.ceil(max(nums) / y) + 1
        while left + 1 < right:
            mid = (right - left) // 2 + left
            if not check(mid):
                left = mid
            else:
                right = mid
        return right

4.执行结果