使数字变为非正数的最少操作次数
Minimum Operations to Make Numbers Non-positive
题目详情
问题:使数字变为非正数的最少操作次数
考察:数组、贪心
来源:Citadel
链接:https://www.jointaro.com/interviews/questions/minimum-operations-to-make-numbers-non-positive/
You are given two positive integer arrays nums1 and nums2.
In one operation, you can choose an index i and subtract 1 from both nums1[i] and nums2[i].
Return the minimum number of operations required to make all elements in at least one of nums1 or nums2 non-positive.
Example 1:
Input: nums1 = [2,3,4,2], nums2 = [1,5,2,4] Output: 5 Explanation: One of the optimal solutions is to perform the following operations: For the first index, we do the operation once, nums1[0] = 1 and nums2[0] = 0. For the second index, we do the operation twice, nums1[1] = 1 and nums2[1] = 3. For the third index, we do the operation once, nums1[2] = 3 and nums2[2] = 1. For the fourth index, we do the operation once, nums1[3] = 1 and nums2[3] = 3. In total we need 1 + 2 + 1 + 1 = 5 operations to make at least one of the arrays non-positive.
Example 2:
Input: nums1 = [2,4,3], nums2 = [2,2,3] Output: 4 Explanation: One of the optimal solutions is to perform the following operations: For the first index, we do the operation once, nums1[0] = 1 and nums2[0] = 1. For the second index, we do the operation once, nums1[1] = 3 and nums2[1] = 1. For the third index, we do the operation twice, nums1[2] = 1 and nums2[2] = 1. In total we need 1 + 1 + 2 = 4 operations to make at least one of the arrays non-positive.
Constraints:
1 <= nums1.length == nums2.length <= 1051 <= nums1[i], nums2[i] <= 109
解析
思路:答案是操作次数,可以二分。给定次数 t,默认每个数都会被减少 t*y;若仍为正,还需要额外选择该数若干次,每次多减少 x-y。统计额外次数是否不超过 t。
复杂度:时间 O(n log answer),空间 O(1)。