找到最高塔的最小可能高度

Question

我有高度 H = h1,h2,h3... 的塔，我有一台切割机，只切割特定长度 A = a1,a2,a3.. 的每个塔，我找到了 m 个切口最高塔的最小可能高度。

for ex- H = 1, 4, 9, 16, 25 and A = 1,2,3,4,5

m = 3（只有 3 次切割）

最小可能高度为 15，因为切割后阵列看起来像 H = 1,4,9,12,15（分别在塔上应用 0、0、0、1、2 切割后）

我尝试了什么：我认为这是贪心问题（如果我错了请纠正我）并且我尝试对 H 数组进行排序并使用一种简单的方法尝试首先减少最大高度直到它不再保持最大然后找到新的最大值并再次应用相同的步骤，这是正确的，但它太天真了，需要大量时间来获取大值？

时间采取步骤：每次都找到最大元素 O(N) 并且排序也不是一个选项（每次）。

n 的限制最大为 10^5，m 的限制约为 10^18。

有没有更好的方法？指导我！！

Answer 1

minimum .. of the maximum .. 形式的问题通常可以通过 二分搜索 的思想来解决。我们可以为给定的问题制定一个 O(N*log(M)) 的解决方案，方法是对度量应用二分搜索来优化，即 minimum possible height of the highest tower。共享相同的伪代码：

start = 0, end = 10^18
while start < end:
    cuts_used = 0 // Number of cuts used till now
    mid = (start + end) / 2
    // Let's see if its possible to trim down all the towers such
    // that height of each tower <= mid
    for i in range(0,N):
        if H[i] > mid:
            // Calculate the number of cuts required to bring H[i]<= mid
            cuts_required = ceil(1.0 * (H[i] - mid) / A[i])
            cuts_used += cuts_required
    // After iterating over the towers
    if cuts_used > M:
        // We're exceeding the number of cuts, hence increase the tower height
        start = mid + 1
    else:
        // We still have some more cuts left, so let's cut more
        end = mid - 1

return start

start应该是我们的最佳答案，因为我们的条件定义为while start < end。考虑我们的范围是开始 = 1 和结束 = 2 的情况。给定情况的中间是 [(1 + 2)/2] = 1。

现在如果 1 确实是我们的最佳答案，那么当 mid = 1 时 cuts_used 将 <= M 并且因此我们的算法将移动到 mid - 1 那是 0。因此范围将是开始 = 1，结束 = 0，我们将停止循环。显然 start 将是我们的解决方案。
现在对于另一种情况，当 2 是解决方案时，cuts_used 对于 mid = 1 将 > M，因此我们的算法将开始移动到 mid + 1 并且范围将变为 start = 2 和 end = 2 - 导致我们停止循环。

无论哪种情况，可见 start 应该是我们的最佳解决方案。

此外，请注意计算 ceil((H[i] - mid) / A[i])，我们不能执行整数除法，因为我们会丢失浮点数，因此 ceil 将无法按预期工作。因此，应该考虑 ceil(1.0 * (H[i] - mid) / A[i]) 将结果类型转换为 float 作为 ceil 的输入。

找到最高塔的最小可能高度

Find minimum possible height of the highest tower

algorithm

math

dynamic-programming

greedy