贪婪算法-最小化完成任务的操作数

Question

我正试图解决一个编程难题。为方便起见，我总结如下：

给定一个正整数的数组A。在一个操作中，我们可以选择数组中元素的一个，Ai并将其减少一个固定数量X。同时，其余的元素将被减少一个固定数量的Y。我们需要找到最小的操作数来将所有元素减少到一个非正数(即0及以下)。 制约因素： 1 <= 1 <= Ai <= 1e9 1 <= Y时限:1秒 来源

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

此示例的最佳方法是：

操作1:选择项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(Ai) /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))。