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

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)。