数组中两个数字之和之间的最小差值

Question

我正在尝试解决此问题：

一位物理教授给班上的学生做项目。学生们必须组成一个两人小组来做这个项目。教授让学生来决定队伍。一个班级的学生人数将是偶数。

每个学生都有自己的知识水平。它告诉每个学生有多少知识。一个团队的知识水平是两个学生知识水平的总和。

学生们决定组成小组，这样知识最高的团队和知识最低的团队之间的差异就最小了。

投入

输入的第一行将包含测试用例的数量t；在接下来的t行中，第一个数字是n，即班级中的学生数量，然后是n个整数，表示n个学生的知识水平

输出

您的输出应该是一行，包含知识最高的团队和知识最低的团队之间可能存在的最小差异。

解决方案归结为计算未排序数组中两个数字之和之间的最小差异。到目前为止，我已经尝试过：

1. 对数组进行排序
2. 将位置i和n-i-1处的元素相加，并将其绝对差与位置i 1和n-i处的元素之和相加
3. 将差异存储在优先级队列中
4. 弹出优先级最高的队列以获得答案

而且，这是我尝试过的代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);

    int T=0,num=0;
    cin >> T;
    
    while(T--){
        cin >> num;
        int *a = new int[num];
        for(int i = 0; i < num; i++){
            cin >> a[i];
        }
        sort(a,a+num);
        priority_queue<int> pq;
        for(int i = 0; i < num-2; i++){
            int j = i+1;
            pq.push(abs(a[i]+a[num-1-i]-a[j]-a[num-j-1]));
        }
        cout << pq.top()<< endl;
    }
    return 0;
}

这个解决方案超出了时间限制，我的直觉是在某些情况下可能会失败。描述和标签暗示了一个动态编程解决方案，但不知何故，我无法推导出最优子结构。有人能帮忙吗？

Answer 1

如果在对数组进行排序后，您开始从两端（第一端到最后一端等）添加值，仅存储最大和最小结果而不是队列，这将有所帮助。然后，您可以通过从最大值中减去最小值来获得答案。

Example: 4 2 6 4 3 1
1. Sort: 1 2 3 4 4 6
2. Iterate:
a. currentValue = a[0] + a[5] = 7; max = min = currentValue = 7
b. currentValue = a[1] + a[4] = 6; max = 7; min = 6
c. currentValue = a[2] + a[3] = 7; max = 7; min = 6
3. Obtain result: difference = max - min = 7 - 6 = 1 

解决方案的简短证明：排序后的值可以这样成像

Answer 2

首先，你是对的，迭代地将剩下的最好的学生和剩下的最差的学生结合起来会给你最佳的结果（见下面的证明）。

但是，您没有正确计算该解决方案的成本。你必须遍历你的组合的所有对，以便找到最好和最差对的质量值，只有在你找到它们之后，你才能减去它们的值。顺便说一句。您不需要优先级队列来查找最小值(它们被认为是用于更复杂的用例，在这些用例中，您需要多次插入和弹出，甚至更新队列中的值)，简单的累加器变量(< code>min和< code>max)就可以了。假设数组< code>a已经排序，代码可能如下所示:

int min = 2 * MAXIMUM_KNOWLEDGE_LEVEL;
int max = 2 * MINIMUM_KNOWLEDGE_LEVEL;
for (int i = 0; i < num / 2; i++) {
    int quality = a[i]+a[num-1-i];
    if (quality < min) {
        min = quality;
    }
    if (quality > max) {
        max = quality;
    }
}
int result = max - min;

现在我想证明为什么你选择的配对(迭代地将最好的剩余学生与最差的剩余学生配对)是最优的，这在这里很重要。如果这不成立，我们需要一个完全不同的算法。

我们通过证明不可能改进配对给出的解决方案来证明这一点。

如果我们想改善它，我们必须减少最佳和最差对之间的差异，这意味着要么降低最佳对，要么提高最差对(或者两者都降低)。

让我们首先说明为什么降低最佳对子是不可能的。

让我们给出对的索引:包含最高数和最低数的对将是p_1 = (a_1，b_1)，具有次高数和次低数的对将是p_2 = (a_2，b_2)等等，直到p_n .例如:

p                   a   b     quality(p)
p_1 = (a_1, b_1) = (10, 1) -> 11 (= min)
p_2 = (a_2, b_2) = ( 9, 4) -> 13
p_3 = (a_3, b_3) = ( 8, 5) -> 13
p_4 = (a_4, b_4) = ( 8, 7) -> 15 (= max)
p_5 = (a_5, b_5) = ( 7, 7) -> 14

其中一对，我们称之为< code>p_m = (a_m，b _ m)(1

在上面的例子中：为了减少15的最大值，所有对的值都必须低于15。这意味着高于或等于最大对（8,8,9,10）的对的所有左侧值都需要低于最大对的右侧伙伴（7）的伙伴，因此只有1,4和5是可能的。

证明提出最差对是不可能的证明与反向比较运算符和切换a和bs的工作方式相同（在这种情况下，我们有太多 s，而 s太少）。

Answer 3

你是对的，通过对第一个元素和最后一个元素进行排序和配对，可以获得最佳排列。(†)

第 2 步和遵循您的方法是错误的。我们不需要优先级队列。我们只需要从创建的对中找到最大和最小总和。

伪代码：

Sort the array.
min = MAX_INT
max = 0
for (i = 0; i < n / 2; i++):
    sum = array[i] + array[n-i-1]
    if (min > sum) min = sum
    if (max < sum) max = sum
return max - min

（†）为什么是这样？

让我们考虑包含< code>1 2 3 6的排序数组。看起来是这样的:

      #
      #
      #
---------- average = 12 / 4 = 3
    # #
  # # #
# # # #

理想情况下，我们以这样的方式配对它们，差值为 0。如果平均值为 3，则理想情况下，平均对将为 6。

好吧，我们不能那样做，我们可以在图像上清楚地看到它。我们只能在低于平均水平的一个地方移动高于平均水平的溢出 3。但是有 2 个这样的地方，大小分别为 2 和 1。

如果我们尽可能填补最大的空白，那就更好了，所以首先在左边。这样我们得到了总和7和5，这有点偏离平均值，但最小——相差1。任何其他配对都将相同或更差。