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

Given N items with values x[1], ..., x[n] and an integer K find a linear time algorithm to arrange these N items in K non empty groups such that in each group the range (difference between minimum and maximum element values/keys in each group) is minimized and therefore the sum of the ranges is minimum.

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

For example given N=4, K=2 and the elements 1 1 4 3 the minimum range is 1 for groups (1,1) and (4,3).

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

2 个解决方案

#1

You can binary search the answer.
Assume the optimal answer is x. Now you should verify whether we can group the items into k groups where the maximum difference between the group items is at most x. This can be done in O(n) [after sorting the array]. Traverse the sorted array and pick consecutive items until the difference between minimum number you have picked for this group and the maximum number you have picked hasn't exceeded x. After that you should initialize a new group and repeat this process. At the end count how many groups you have made. If the number of groups is more than k we can conclude that we can not group the items in k groups with x being the answer. So we should increase x. By binary searching on x we can find the minimum x.

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

The overall complexity is O(NlogN).

整体复杂度为O(NlogN)。

Here is a sample implementation in C++

下面是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;

}

#2

Alright, I'll assume that we want to minimize the sum of differences over all groups.

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

Let's sort the numbers. There's an optimal answer where each group is a consecutive segment in the sorted array (proof: let A1 < B1 < A2 < B2. We can exchange A2 and B1. The answer will not increase).

让我们的数字。有一个最佳答案，每个组都是排序数组中的连续段(证明:让A1 < B1 < A2 < B2)。我们可以交换A2和B1。答案不会增加)。
Let a[l], a[l + 1], ..., a[r] is a group. It's cost is a[r] - a[l] = (a[r] - a[r - 1]) + (a[r - 1] - a[r - 2]) + ... + (a[l + 1] - a[l]). It leads us to a key insight: k groups is k - 1 gaps and the answer is a[n - 1] - a[0] - sum of gaps. Thus, we just need to maximize the gaps.

让a[l]， a[l + 1]，……， a[r]是一个群。成本是一个[r]——[l]=((r)-(r - 1))+((r - 1][r - 2])+…+ (a[l + 1] - a[l])这让我们得出一个关键的结论:k组是k - 1的差值，答案是[n - 1] -[0] -差值的和。因此，我们只需要最大限度地缩小差距。
Here is a final solution:

最后的解决办法是:
- sort the array
- 排序数组
- compute differences between adjacent numbers
- 计算相邻数之间的差异
- take k - 1 largest differences. That's exactly where the groups split.
- 取k - 1最大的差值。这正是群体分裂的地方。
- We can find the k-1th largest element in linear time (or if we are fine with O(N log N) time, we can just sort them). That's it.
- 我们可以找到线性时间中k-1最大的元素(或者如果我们对O(N log N)时间没问题的话，我们可以对它们进行排序)。就是这样。

Here is an example:

这是一个例子:

x = [1, 1, 4, 3], k = 2
sorted: [1, 1, 3, 4]
differences: [0, 2, 1]
taking k - 1 = 1 largest gaps: it's 2. Thus the groups are [1, 1] and [3, 4].

x =[1、1、4、3]，k = 2排序:[1、1、3、4]差异:[0、2、1]取k - 1 = 1最大的间隔为2。因此组是[1,1]和[3,4]。

A slightly more contrived one:
x = [8, 2, 0, 3], k = 3
sorted: [0, 2, 3, 8]
differences: [2, 1, 5]
taking k - 1 = 2 largest gaps: they're 2 and 5. Thus, the groups are [0], [2, 3], [8] with the total cost of 1.

一个略显人为的:x = [8,2,0,3]， k = 3排序:[0,2,3,8]差异:[2,1,5]取k - 1 = 2最大的差距:它们是2和5。因此，组为[0]，[2,3]，[8]，总成本为1。

#1