时间戳

首页 > 解决方案 > 找到最高塔的最小可能高度

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

问题描述

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

对于 ex- H = 1, 4, 9, 16, 25 和 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。

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

标签： algorithmmathdynamic-programminggreedy

解决方案

形式minimum .. of the maximum ..的问题通常可以通过二分搜索的思想来解决。我们可以通过对度量应用二分搜索来优化给定问题，即 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。考虑我们的范围是 start = 1 和 end = 2 的情况。给定情况的中间值是 [(1 + 2)/2] = 1。

  • 现在如果1确实是我们的最佳答案，那么当 mid = 1 时 cut_used 将 <= M 并且因此我们的 alogirthm 将移动 end 到 mid - 1 即 0。因此范围将是 start = 1，end = 0 并且我们'将停止循环。显然start将是我们的解决方案。

  • 现在对于解决方案的另一种情况2，用于 mid = 1 的 cuts_used 将 > 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 的输入。

推荐阅读