返回题库

使数字变为非正数的最少操作次数

Minimum Operations to Make Numbers Non-positive

专题
Algorithmic Programming / 算法编程
难度
L4
来源
Citadel

题目详情

问题:使数字变为非正数的最少操作次数

考察:数组、贪心

来源: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 <= 105
  • 1 <= nums1[i], nums2[i] <= 109
解析

思路:答案是操作次数,可以二分。给定次数 t,默认每个数都会被减少 t*y;若仍为正,还需要额外选择该数若干次,每次多减少 x-y。统计额外次数是否不超过 t。

复杂度:时间 O(n log answer),空间 O(1)。