塔高之间的最小差异? [英] Minimum difference between heights of Towers?

问题描述

我正在经历一些面试问题，我看到了这个问题

您将获得n个塔的高度和k值.您必须将每个塔的高度增加或减少k.您需要最小化最长和最短塔架高度之间的差异，并输出该差异.

我认为答案将是(maxheight-k)-(minheight + k).我已经尝试了一些运行良好的测试用例.

但是我不确定，我想我缺少了什么，是吗?

解决方案

m7thon的答案解释了您的解决方案存在的问题，因此，我仅说明您如何实际解决此问题..

要观察的一件大事是，对于任何给定的塔，如果您选择将其高度从 h _i 增大到h _i + k ，那么您也可以增加所有较短塔的高度:不会影响最大塔数(因为如果 h _j < h _i ，然后 h _j + k h _i + k )，而 可能会增加最小值.相反，如果您选择将塔的高度从 h _i 降低到 h em> _i − k ，那么您最好降低所有较高塔的高度.

因此，虽然有2 ⁿ 种可能的方法来选择应该增加还是减少的塔楼，我们实际上可以忽略其中的大多数.一些塔将成为我们增加高度的最高塔；对于所有较短的塔，我们也将增加它们的高度，对于所有较高的塔，我们将降低它们的高度.因此，只有 n 有趣的方法来选择应该增加还是减少的塔楼:每座塔楼成为我们增加高度的最高塔楼的机会之一./p>

[脚注1:您可能会注意到，降低所有塔的高度也是有效的，在这种情况下，没有这样的塔.但这等同于增加所有塔楼的高度-无论我们向每个高度添加 k 还是从每个高度减去 k ，无论哪种方式，并没有实际更改max-min-min.]

[书注2:我只提到了较短的塔楼"塔楼"和塔楼塔"，但也有可能多个塔楼具有相同的初始高度.但是这种情况并不是很重要，因为我们可能会全部增加或减少全部-没有必要增加一些而减少其他.因此，这里描述的方法仍然可以正常工作.]

因此，让我们从对原始高度进行排序并按升序对它们进行编号，以使 h ₁ 是原始最短塔和的原始高度.> h _n 是最初最高的塔的原始高度.

对于每个 i ，尝试以下可能性:最短的 i 塔是我们增加高度的最高塔；也就是说，尝试通过 h _i 增加 h ₁ 的可能性，然后通过 h _n 减少 h _{i +1} .有两种情况:

• 如果 i n ，则最后最短的塔的最终高度为min( h ₁ + k ， h _{i +1} − k )，最后一座最高塔的最终高度为max(h _i + k ， h _n - k ).在这种情况下，最终的区别是后者减去前者.
• 如果 i = n ，那么我们平均增加了所有塔的高度，因此最终差异只是 h _n - h ₁ .

然后，我们将所有这些可能性中的 n 差异最小.

这是一个实现此方法的Java方法(假定 int 值的高度；请注意， h _i 是 arr [i-1] 和 h _{i +1} 是 arr [i] ):

  private静态int doIt(final int [] arr，final int k){java.util.Arrays.sort(arr);final int n =长度int结果= arr [n-1]-arr [0];对于(int i = 1; i< n; ++ i){final int min = Math.min(arr [0] + k，arr [i]-k);final int max = Math.max(arr [n-1]-k，arr [i-1] + k);结果= Math.min(result，max-min);}返回结果；} 

请注意，为方便起见，我在循环之前拉了 i == n 案例.

I was going through some interview questions, I saw this one

You are given the height of n towers and value k. You have to either increase or decrease the height of every tower by k. You need to minimize the difference between the height of the longest and the shortest tower and output this difference.

I think the answer will be (maxheight-k) - (minheight + k). I have tried on some test cases it is running fine.

But I am not sure, I think I am missing something, Am I ?

解决方案

m7thon's answer explains the problem with your solution, so I'll just explain how you can actually solve this . . .

The big thing to observe is that for any given tower, if you choose to increase its height from h_i to h_i + k, then you might as well increase the height of all shorter towers: that won't affect the maximum (because if h_j < h_i, then h_j + k < h_i + k), and may help by increasing the minimum. Conversely, if you choose to decrease the height of a tower from h_i to h_i − k, then you might as well decrease the heights of all taller towers.

So while there are 2ⁿ possible ways to choose which towers should be increased vs. decreased, we can actually ignore most of these. Some tower will be the tallest tower that we increase the height of; for all shorter towers, we will increase their height as well, and for all taller towers, we will decrease their height. So there are only n interesting ways to choose which towers should be increased vs. decreased: one for each tower's chance to be the tallest tower that we increase the height of.

[Pedantic note #1: You may notice that it's also valid to decrease the heights of all towers, in which case there's no such tower. But that's equivalent to increasing the heights of all towers — whether we add k to every height or subtract k from every height, either way we're not actually changing the max-minus-min.]

[Pedantic note #2: I've only mentioned "shorter towers" and "taller towers", but it's also possible that multiple towers have the same initial height. But this case isn't really important, because we might as well increase them all or decrease them all — there's no point increasing some and decreasing others. So the approach described here still works fine.]

So, let's start by sorting the original heights and numbering them in increasing order, so that h₁ is the original height of the originally-shortest tower and h_n is the original height of the originally-tallest tower.

For each i, try the possibility that the ith-shortest tower is the tallest tower that we increase the height of; that is, try the possibility that we increase h₁ through h_i and decrease h_i+1 through h_n. There are two groups of cases:

• If i < n, then the final height of the finally-shortest tower is min(h₁ + k, h_i+1 − k), and the final height of the finally-tallest tower is max(h_i + k, h_n − k). The final difference in this case is the latter minus the former.
• If i = n, then we've increased the heights of all towers equally, so the final difference is just h_n − h₁.

We then take the least difference from all n of these possibilities.

Here's a Java method that implements this (assuming int-valued heights; note that h_i is arr[i-1] and h_i+1 is arr[i]):

private static int doIt(final int[] arr, final int k) {
    java.util.Arrays.sort(arr);
    final int n = arr.length;
    int result = arr[n - 1] - arr[0];
    for (int i = 1; i < n; ++i) {
        final int min = Math.min(arr[0] + k, arr[i] - k);
        final int max = Math.max(arr[n - 1] - k, arr[i - 1] + k);
        result = Math.min(result, max - min);
    }
    return result;
}

Note that I've pulled the i = n case before the loop, for convenience.

这篇关于塔高之间的最小差异?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！