查找最高塔的最小可能高度 [英] Find minimum possible height of the highest tower

问题描述

我有高度为H = h1，h2，h3 ...的塔，并且我有一台切割机，仅切割具有特定长度A = a1，a2，a3 ..的每座塔，并且我有m次切割找到最小值最高塔的可能高度.

I have towers with height H = h1,h2,h3... and i have a cutting machine that only cuts each tower with a specific length A = a1,a2,a3.. and i have m cuts find the minimum possible height of the highest tower.

对于ex- H = 1，4，9，16，25和A = 1,2,3,4,5

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

m = 3(仅3切)

m = 3 ( only 3 cuts )

最小可能的高度是15，因为切割后的数组看起来像H = 1,4,9,12,15(分别在塔上应用0、0、0、1、2切割后)

the minimum possible height is 15 as after cuts the array looks like H = 1,4,9,12,15 ( after applying 0, 0 , 0, 1, 2 cuts respectively on towers)

我尝试的方法:我认识到它是贪婪的问题(如果我错了，请纠正我)，然后我尝试对H数组进行排序，并尝试使用一种简单的方法先将最大高度减小到不再保持最大高度，然后再减小找到了新的最大值，然后再次应用相同的步骤，这是正确的，但是它太幼稚了，要花费大量时间来获取较大的值?

What I tried : I recognised it as greedy problem (correct me if i am wrong) and i tried to sort the H array and with a simple approach tried to cut down first the maximum height till it no longer remains maximum and then found the new maximum and again applied the same steps, it's correct but it's too naive and taking huge amount of time for large values?

采取时间步骤:每次O(N)都查找最大元素，也不是每次都进行排序.

Time taking steps : finding maximum element each time O(N) and sorting is also not an option (every time).

n的约束最大为10 ^ 5，m的约束大约为10 ^ 18.

Constraints for n are upto 10^5 and m are around 10^18.

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

Is there any better approach? Guide me!!

推荐答案

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

Questions of the form minimum .. of the maximum .. are generally approachable by the idea of a binary search. We can formulate an O(N*log(M)) solution for the given question by applying a binary search over the metric to optimize that is, minimum possible height of the highest tower. Sharing a pseudocode for the same:

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.

start should be our optimal answer, since our condition is defined as while start < end. Consider the case wherein our range is, start = 1 and end = 2. The mid for the given case is [(1 + 2)/2] = 1.

• 现在，如果1确实是我们的最佳答案，那么当mid = 1时cuts_used将等于< = M，因此我们的对数将移至中间-1(即0).因此，范围将是开始= 1，结束= 0，我们将停止循环.显然，start将是我们的解决方案.

• Now If 1 is indeed our optimal answer, then cuts_used when mid = 1 will be <= M and hence our alogirthm will move end to mid - 1 that is, 0. Hence the range will be start = 1, end = 0 and we'll stop looping. Clearly start will be our solution.

现在对于2是解决方案的另一种情况，中= 1的cuts_used将> M，因此我们的算法将开始移动到中+ 1，范围将变为开始= 2和结束= 2-导致我们停止循环播放.

Now for the other case when 2 is the solution, cuts_used for mid = 1 will be > M and hence our algorithm will move start to mid + 1 and the range will become start = 2 and end = 2 - causing us to stop looping.

在任何一种情况下，很明显start应该是我们的最佳解决方案.

In either of the cases, it's visible that start should be our optimal solution.

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

Also, please note for computing ceil((H[i] - mid) / A[i]), we must not carry out an integer division since we'll lose the floating point and hence ceil will not work as intended. Therefore, ceil(1.0 * (H[i] - mid) / A[i]) should be considered to typecast the result to float for the input for ceil.

这篇关于查找最高塔的最小可能高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！