logo标签列表

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

c++arraysoptimizationgreedy
13

给定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; 
}

有人能帮我提供这个问题的正确解决方案吗？

2
一些推荐阅读：为什么不应该使用#include <bits/stdc++.h>？和为什么认为using namespace std;是不好的编程习惯？ - ChrisMM
你遇到了什么问题？“有人能帮我提供正确的解决方案吗？”这不是一个在SO上会受到良好回应的问题。 - ChrisMM
这个回答解决了您的问题吗？塔之间最小高度差？ - Go Beyond
这个链接很好地解释了这个问题。 - DEEPANSHU RAWAT
7个回答
29

上面的代码是可行的，但我觉得缺乏解释，所以我会尝试添加一些解释来帮助培养直觉。

对于任何给定的建筑物，你有两个选择，你可以增加它的高度或者减少它的高度。
现在如果你决定将其高度从 Hi 增加到 Hi + K，那么你也可以增加所有较矮的建筑物的高度，因为这不会影响最大值。同样地，如果你决定将一个塔的高度从 Hi 减小到 Hi − K，那么你也可以降低所有更高的建筑物的高度。
我们将利用这个性质，有n座建筑物，我们将尝试使每座建筑物都尽可能高，并看看哪座建筑物的高度最高，这样可以得到最小的高度范围（这就是我们的答案）。
让我解释一下：

所以我们要做的是 -
1）首先对数组进行排序（您很快就会看到原因）。

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

所以，假设我们在i楼房上，我们已经将K添加到了该建筑物和它之前的建筑物，并从它之后的建筑物中减去了K。

因此，建筑物的最小高度现在将是min（0 + K，< H >i+1 - K），即 min（第一座建筑物 + K，右边的下一个建筑物 - K）。

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

同样，建筑物的最大高度将是 max（i + K，< H >n-1 - K），即 max（当前建筑物 + K，右边的最后一座建筑物 - K）。

3）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;
    }
}
3
很好的解释。 - Saurabh Dhage
1
很好的解释！ - Embydextrous
5
int getMinDiff(int a[], int n, int k) {
        sort(a,a+n); 
        int i,mx,mn,ans;
        ans = a[n-1]-a[0];  // this can be one possible solution
        
        for(i=0;i<n;i++)
        {
            if(a[i]>=k)  // since height of tower can't be -ve so taking only +ve heights
            {
                mn = min(a[0]+k, a[i]-k);
                mx = max(a[n-1]-k, a[i-1]+k);
                ans = min(ans, mx-mn);
            }
        }
        return ans;
    }

这是C++代码，它通过了所有的测试用例。

3
你能告诉我它为什么有效吗？我没有理解其背后的直觉。虽然在问题中分享的代码是错误的。 - rahul sharma
索引应该从1开始，以避免越界异常。 - curious_soul
4
这段Python代码可能对您有所帮助。代码本身就很清楚明了。
def getMinDiff(arr, n, k):
    arr = sorted(arr)
    ans = arr[-1]-arr[0] #this case occurs when either we subtract k or add k to all elements of the array
    for i in range(n):
        mn=min(arr[0]+k, arr[i]-k) #after sorting, arr[0] is minimum. so adding k pushes it towards maximum. We subtract k from arr[i] to get any other worse (smaller) minimum. worse means increasing the diff b/w mn and mx
        mx=max(arr[n-1]-k, arr[i]+k) # after sorting, arr[n-1] is maximum. so subtracting k pushes it towards minimum. We add k to arr[i] to get any other worse (bigger) maximum. worse means increasing the diff b/w mn and mx
        ans = min(ans, mx-mn)
    return ans
还要添加if语句来检查arr[i]是否大于k。我们不能有负高度，不是吗？ - Nikhil.Nixel
1
@rahulsharma 我在代码中添加了一些注释，看看是否有帮助。尝试运行代码，你会得到直觉。 - Himanshu Singh
1

以下是解决方案：

但在介绍解决方案之前，需要了解一些信息。在最理想的情况下，最小差异为零。这只可能发生在两种情况下 - （1）数组包含重复项或（2）对于一个元素，比如“x”，存在另一个元素具有值“x + 2 * k”。

思路非常简单。

  1. 首先，我们将排序数组。
  2. 接下来，我们将尝试使用二分查找找到最佳值（其答案为零），或者至少找到最接近最佳值的数字

以下是算法的Javascript实现：

function minDiffTower(arr, k) {
    arr = arr.sort((a,b) => a-b);
    let minDiff = Infinity;
    let prev = null;

    for (let i=0; i<arr.length; i++) {
        let el = arr[i];
        
        // Handling case when the array have duplicates
        if (el == prev) {
            minDiff = 0;
            break;
        }
        prev = el;

        let targetNum = el + 2*k; // Lets say we have an element 10. The difference would be zero when there exists an element with value 10+2*k (this is the 'optimum value' as discussed in the explaination
        let closestMatchDiff =  Infinity; // It's not necessary that there would exist 'targetNum' in the array, so we try to find the closest to this number using Binary Search
        let lb = i+1;
        let ub = arr.length-1;
        while (lb<=ub) {
            let mid = lb + ((ub-lb)>>1);
            let currMidDiff =  arr[mid] > targetNum ? arr[mid] - targetNum : targetNum - arr[mid];
            closestMatchDiff = Math.min(closestMatchDiff, currMidDiff); 
            if (arr[mid] == targetNum) break; // in this case the answer would be simply zero, no need to proceed further
            else if (arr[mid] < targetNum) lb = mid+1;
            else ub = mid-1;
        }
        minDiff = Math.min(minDiff, closestMatchDiff);
    }
    return minDiff;
}
0
class Solution {
  public:
    int getMinDiff(int arr[], int n, int k) {
            sort(arr, arr+n);
        int diff = arr[n-1]-arr[0];
        int mine, maxe;
        for(int i = 0; i < n; i++)
            arr[i]+=k;
        mine = arr[0];
        maxe = arr[n-1]-2*k;
        for(int i = n-1; i > 0; i--){
            if(arr[i]-2*k < 0)
                break;
            mine = min(mine, arr[i]-2*k);
            maxe =  max(arr[i-1], arr[n-1]-2*k);
            diff = min(diff, maxe-mine);
        }
        return diff;
    }
};
0
class Solution:
    def getMinDiff(self, arr, n, k):
        # code here
        arr.sort()
        res = arr[-1]-arr[0]
        
        for i in range(1, n):
            if arr[i]>=k:
                # at a time we can increase or decrease one number only. 
                # Hence assuming we decrease ith elem, we will increase i-1 th elem.
                # using this we basically find which is new_min and new_max possible 
                # and if the difference is smaller than res, we return the same. 
                new_min = min(arr[0]+k, arr[i]-k)
                new_max = max(arr[-1]-k, arr[i-1]+k)
                res = min(res, new_max-new_min)
        
        return res
请添加更多细节以扩展您的答案，例如工作代码或文档引用。 - Community
0

这里是C++代码，我从你离开的地方继续。代码是自解释的。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDiff(int arr[], int n, int k)
{
    // If the array has only one element.
    if (n == 1)
    {
        return 0;
    }
    //sort all elements
    sort(arr, arr + n);

    //initialise 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 the elements to keep the array sorted.
        int temp = small;
        small = big;
        big = temp;
    }

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

        // If both subtraction and addition do not change the diff.
        // Subtraction does not give new minimum.
        // Addition does not give new maximum.
        if (subtract >= small or 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);
}

int main(void)
{
    int arr[] = {1, 5, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "\nMaximum difference is: " << minDiff(arr, n, k) << endl;
    return 0;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接