algorithm - 数组中最大元素的最小化

Question

您有一个大小n为正整数的数组，您最多可以在其上执行以下操作N：

• 选择一个子数组并将其元素值减少k（k必须小于子数组的最小值）。
• 这种操作的代价是子数组的大小乘以k。
• 这些操作的总成本不得大于M。
• NM 可以非常大。

你能给我一个有效的算法来最小化这个数组中的最大元素吗？

Answer 1

如果我们可以创建一个函数来检查是否可以达到给定的最大值，那么我们可以使用对最大值的二进制搜索来找到解决方案。（每次可以达到最大值时，减少它，如果它不能实现，增加它）。

检查功能可能如下所示：

def check(array, M, i, j, max)

如果有可能以 M 成本将 i 和 j 之间的所有内容减少到最大值以下，这将返回 true。我们从i=0, j=len(array), max=max_guess

你现在有很多选项来做内部检查。你可以试试：

possible = check(M/2, i..i+j/2, ..) and check(M/2, i..i+j/2,..)
return possible

但是将 M 分成两半并不是一个好主意，因为一半可能需要更多。也许您可以使用二进制搜索来确定如何将 M 分成两半。但是，也许甚至不可能将数组分成两半，因为某些小节可能会超过两半，所以也许您需要在其他地方拆分？或者您可能需要尝试 i,j 的所有组合进行拆分。

祝你好运。

Answer 2

假设我们选择 x 作为缩减数组中的最大数，我们可以取数组并将其所有较大的元素减少到 x 并计算这些操作的成本及其数量，然后我们可以尝试贪婪地加入这些中最便宜（成本）的子集元素，直到操作数小于 N。如果成本大于 M，则缩减数组中的最大元素必须更大。对于 x，我们可以轻松地对它进行二分查找。

Answer 3

老实说，我很怀疑找到这个问题的最佳解决方案是 NP 难的。我承认这并不是特别有帮助，但它可能会让您对如何处理这是其中一部分的更大问题有不同的看法。