最小化高度之间的最大差异

Question

给定 n 个塔的高度和一个值 k。我们需要将每个塔的高度增加或减少 k（仅一次），其中 k > 0。任务是最小化修改后最长和最短塔的高度之间的差异，并输出该差异。

我得到了解决方案背后的直觉，但我无法评论下面解决方案的正确性。

// C++ program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
#include <bits/stdc++.h>
using namespace std;

// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
int getMinDiff(int arr[], int n, int k)
{
    if (n == 1)
       return 0;

    // Sort all elements
    sort(arr, arr+n);

    // Initialize result
    int ans = arr[n-1] - arr[0];

    // Handle corner elements
    int small = arr[0] + k;
    int big = arr[n-1] - k;
    if (small > big)
       swap(small, big);

    // Traverse middle elements
    for (int i = 1; i < n-1; i ++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;

        // If both subtraction and addition
        // do not change diff
        if (subtract >= small || add <= big)
            continue;

        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if (big - subtract <= add - small)
            small = subtract;
        else
            big = add;
    }

    return  min(ans, big - small);
}

// Driver function to test the above function
int main()
{
    int arr[] = {4, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 10;
    cout << "\nMaximum difference is "
        << getMinDiff(arr, n, k);
    return 0;
}

谁能帮我为这个问题提供正确的解决方案？

原文由 Ajay Singh 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

上面的代码有效，但是我没有找到太多解释，所以我会尝试添加一些以帮助培养直觉。

对于任何给定的塔，您有两种选择，您可以增加它的高度或降低它。

现在，如果您决定将其高度从 H _i_增加到 H i + K ，那么您还可以增加所有较短塔的高度，因为这不会影响最大值。

同样，如果您决定将塔的高度从 H _i_降低到 H i - K ，那么您也可以降低所有较高塔的高度。

我们将利用这一点，我们有 n 座建筑物，我们将尝试使每座建筑物都最高，看看哪座建筑物最高给我们的高度范围最小（这是我们的答案）。

让我解释：

所以我们想做的是——

1）我们首先对数组进行排序（你很快就会明白为什么）。

2）然后对于从 i = 0 到 n-2 [1]的每一栋建筑物，我们尝试使其最高（通过将 K 添加到建筑物，将 K 添加到其左侧的建筑物并从其右侧的建筑物中减去 K ）。

假设我们正在建造 H i ，我们将 K 添加到它和它之前的建筑物中，并从它之后的建筑物中减去 K。

所以建筑物的最小高度现在将是 min( H 0 + K , H i+1 - K )，

即 min(1st building + K, next building on right - K) 。

（注意：这是因为我们对数组进行了排序。举几个例子说服自己。）

同样，建筑物的最大高度将是 max( H i + K , H n-1 - K )，

即 max(current building + K, last building on right - K) 。

1. max - min 为您提供范围。

[1]注意当 i = n-1 时。在这种情况下，当前建筑物之后没有建筑物，因此我们将 K 添加到每个建筑物中，因此范围将仅为 height[n-1] - height[0]，因为 K 被添加到所有内容中，所以它取消出去。

这是基于上述想法的Java实现：

 class Solution {
    int getMinDiff(int[] arr, int n, int k) {
        Arrays.sort(arr);
        int ans = arr[n-1] - arr[0];
        int smallest = arr[0] + k, largest = arr[n-1]-k;
        for(int i = 0; i < n-1; i++){
            int min = Math.min(smallest, arr[i+1]-k);
            int max = Math.max(largest, arr[i]+k);
            if (min < 0) continue;
            ans = Math.min(ans, max-min);
        }
        return ans;
    }
}

原文由 Ayush 发布，翻译遵循 CC BY-SA 4.0 许可协议