在 k 个非空组中排列 n 个项目，以便最小化每个组的最小元素和最大元素之间的差异

Question

给定 N 个值

为 x[1], ..., x[n] 和整数 K 的项目，找到一个线性时间算法，将这 N 个项目排列在 K个非空组中，以便在每个组中将范围(每个组中的最小和最大元素值/键之间的差异(最小化，因此范围的总和最小。

例如，给定N=4、K=2和元素1 1 4 3最小范围是1组(1,1)和(4,3)。

Answer 1

您可以二叉搜索答案。
假设最佳答案是 x。现在您应该验证我们是否可以将项目分组为 k 组，其中组项目之间的最大差异最多为 x。这可以在 O(n( 中完成 [在对数组进行排序后]。遍历排序后的数组并选取连续的项目，直到您为此组选择的最小数量与您选择的最大数量之间的差异不超过 x。之后，您应该初始化一个新组并重复此过程。最后数一数你做了多少组。如果组的数量大于 k，我们可以得出结论，我们不能将项目分组到 k 组中，x 是答案。所以我们应该增加 x。通过在 x 上进行二进制搜索，我们可以找到最小值 x。

整体复杂度为 O(NlogN(。

下面是C++中的示例实现

#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    int n = 4, k = 2;
    std::vector<int> v = {1, 1, 4, 3};
    sort(v.begin(), v.end());
    int low = 0, high = *max_element(v.begin(), v.end());
    while ( low < high ){
        int x = (low+high)/2;
        int groups = 0;
        int left = 0;
        while (left < v.size()){
            int right = left;
            while( right < v.size() && v[right] - v[left] <= x ){
                ++right;
            }
            ++groups;
            left = right;
        }
        // printf("x:%d groups:%dn", x, groups );
        if (groups > k)
        {
            low = x + 1;
        } else {
            high = x;
        }
    }
    cout << "result is " << low << endl;
}

Answer 2

好吧，我假设我们希望最小化所有组的差异总和。

1. 让我们对数字进行排序。有一个最佳答案，其中每个组是排序数组中的一个连续段(证明：设 A1

2. 设 a[l]， a[l + 1]， ...， a[r] 是一个群。它的成本是a[r] - a[l] = (a[r] - a[r - 1]) + (a[r - 1] - a[r - 2]) + ... + (a[l + 1] - a[l]).它引导我们得出一个关键的见解：k群体k - 1差距，答案是a[n - 1] - a[0] - sum of gaps 。因此，我们只需要最大化差距。

3. 这是最终解决方案：

   • 对数组进行排序
   • 计算相邻数字之间的差异
   • k - 1最大的差异。这正是团体分裂的地方。
   • 我们可以在线性时间中找到第 k-1 个最大的元素(或者如果我们对时间没问题O(N log N)我们可以对它们进行排序(。就是这样。

下面是一个示例：

x = [1, 1, 4, 3], k = 2排序： [1, 1, 3, 4]
差异：[0, 2, 1]
取k - 1 = 1最大的差距：它是2。因此，这些组是[1, 1]和[3, 4]的。

一个稍微做作的：

x = [8, 2, 0, 3], k = 3排序： [0, 2, 3, 8]
差异：[2, 1, 5]
取k - 1 = 2最大的差距：它们是 2 和 5。因此，这些组的总成本为 1 [0], [2, 3], [8]。