将 n 项排列在 k 个非空组中，使得每个组的最小元素和最大元素之间的差异最小

Question

给定 N 个值 x[1], ..., x[n] 的项目和一个整数 K 找到一个线性时间算法来排列这些 N K 个非空组中的项目，这样每个组中的范围（每个组中最小和最大元素 values/keys 之间的差异）被最小化并且因此范围的总和是最小的。

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

Answer 1

好的，我假设我们想要最小化所有组的差异总和。

让我们对数字进行排序。有一个最佳答案，每组是排序数组中的连续段（证明：令A1 < B1 < A2 < B2。我们可以交换A2和B1。答案不会增加）。
设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。因此，我们只需要最大化差距。
这是最终的解决方案：
- 对数组进行排序
- 计算相邻数字之间的差异
- 取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。因此，这些组是 [0], [2, 3], [8]，总成本为 1。

Answer 2

您可以二分搜索答案。
假设最佳答案是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:%d\n", x, groups );
        if (groups > k)
        {
            low = x + 1;
        } else {
            high = x;
        }
    }

    cout << "result is " << low << endl;

}

将 n 项排列在 k 个非空组中，使得每个组的最小元素和最大元素之间的差异最小

Arrange n items in k nonempty groups such that the difference between the minimum element and the maximum element of each group is minimized

algorithm

dynamic-programming

greedy