c++ - 数组中两个数之和的最小差值

Question

我正在尝试解决这个问题 problem :

A Professor of Physics gave projects to the students of his class. The students have to form a team of two for doing the project. The professor left the students to decide the teams. The number of students in a class will be even.

Each student has a knowledge level. It tells how much knowledge each student has. The knowledge level of a team is the sum of the knowledge levels of both the students.

The students decide to form groups such that the difference between the team with highest knowledge and the one with lowest knowledge is minimum.

Input

First line of the input will contain number of test cases t; In the next t lines the first number is n the number of students in the class followed by n integers denoting the knowledge levels of the n students

Output

Your output should be a single line containing the lowest possible difference between the team with highest knowledge and the one with lowest knowledge.

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

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

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

您的方法中的第 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

---

(†) 为什么是这样？

让我们考虑包含 1 2 3 6 的排序数组。它看起来像这样:

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

理想情况下，我们以差异为 0 的方式对它们进行配对。如果平均值为 3，那么理想情况下，平均配对将为 6。

好吧，我们不能那样做，我们可以在图像上清楚地看到它。我们只能在平均水平以下的一个位置移动超过平均水平的 3。但是有 2 个这样的地方，大小为 2 和 1。

如果我们填补尽可能大的空白会更好，所以首先在左边。通过这种方式，我们得到了总和 7 和 5，它们有点偏离平均值，但最低限度为 1。任何其他配对将相同或更差。