使数字变为非正数的最少操作次数
Minimum Operations to Make Numbers Non-positive
题目详情
问题：使数字变为非正数的最少操作次数
考察：数组、二分查找
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/minimum-operations-to-make-numbers-non-positive
英文原题
Problem: Minimum Operations to Make Numbers Non-positive
Patterns: Array, Binary Search
Recency: 2yr
Link: https://leetcode.com/problems/minimum-operations-to-make-numbers-non-positive
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：答案是操作次数，可以二分。给定次数 t，默认每个数都会被减少 t*y；若仍为正，还需要额外选择该数若干次，每次多减少 x-y。统计额外次数是否不超过 t。
复杂度：时间 O(n log answer)，空间 O(1)。
英文解析
Approach: Binary-search the number of operations `t`. After `t` global decreases by `y`, any still-positive number needs extra selected operations, each giving an additional decrease of `x-y`; the guess is feasible if the total extra selections is at most `t`.
Complexity: Time , space .