贪心算法——最小化完成任务的操作次数

Question

我正在尝试解决编程难题。为了方便起见，我总结如下：

Given an array, A, of positive integers. In one operation, we can choose one of the elements in the array, A[i] and reduce it by a fixed amount X. At the same time, the rest of the elements will be reduced by a fixed amount Y. We need to find the minimum number of operations to reduce all elements to a non-positive number (i.e. 0 and below).

Constraints:
1 <= |A| <= 1e5
1 <= A[i] <= 1e9
1 <= Y < X <= 1e9
Time limit: 1 second

Source

例如，设 X = 10，Y = 4 和 A = {20, 20}。

此示例的最佳方法是：

操作一：选择项目0。

A = {10, 16}

操作2：选择项目0。

A = {0, 12}

操作3：选择项目1。

A = {-4, 2}

操作4：选择项目1。

A = {-8, -8}

因此，答案是 4。

我的做法：

继续选择数组中的当前最大元素并将其减少X（并将其余元素减少Y）。显然，由于 X 和 Y 的值可能很小（即我的算法将执行的迭代次数下限为 max(A[i]) / 2），这种方法会超过时间限制。

有人可以告诉我更好的解决方案吗？

Answer 1

这个问题可以用二分查找来解决

首先，我们要检查在a次操作中，能否让所有元素都变成<=0；我们可以检查每个元素的最小操作数 b，这样如果我们为 b 操作减去 x 并为剩余的 a-b 减去 y ] 操作，则元素的结果值将变为 <= 0。将所有这些数字加在一起，如果 sum <= a，这意味着我们可以使用 a 操作。

然后，我们可以应用二进制搜索来搜索有效的 a。

int st = 0;
int ed = max element / y + 1;
int result = ed;
while(start <= end){
    int mid = (st + ed)/2;
    int sum = 0;
    for(int i : A){
        sum += minTimesMinusX(i, mid);
    }
    if(sum <= mid){
        result = mid;
        ed = mid - 1;
    }else{
        st = mid + 1;
    }
}
return result;

时间复杂度O(n log max(A)).

贪心算法——最小化完成任务的操作次数

Greedy algorithm - minimize number of operations to complete task

algorithm

greedy