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

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.

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

对数组进行排序。
将位置i和n-i-1的元素相加，取其与位置i+1和n-i的元素之和的绝对差
将差异存储在优先级队列中。
弹出优先队列的顶部以获得答案。

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

#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。任何其他配对都会相同或更差。

Answer 2

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

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

解决方案的简短证明：排序后的值可以这样成像a<=b<=c...<=k<=n。让我们假设现在所有值都是不同的，所以 a < b < c <...< k < n。如果值不同，则 (b-a>=1) 因此 (b=>a+1) 以及 (n=>k+1)。对于 a+n 和 b+k，差异至少为 (a+n)-(b+k)=(a+n)-(a+1+n-1)=0。对于 a+k 和 b+n，差异至少为 (b+n)-(a+k)=(a+1+n)-(a+n-1)=2。这可以扩展为 a<=c 等等。如果某些值相同，则替换将无效。

Answer 3

首先，您是对的，将剩余最好的学生与剩余最差的学生迭代组合可以得到最佳结果（见下面的证明）。

但是，您没有正确计算该解决方案的成本。您必须运行遍历所有组合对才能找到最佳和最差对的质量值，并且只有在找到它们之后才能减去它们的值。顺便提一句。您不需要优先级队列来找到最小值（它们被认为用于更复杂的用例，其中您插入和弹出几次甚至更新队列中的值），简单的累加器变量（min 和 max）就可以了。假设数组 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

现在，其中一对，我们称之为 p_m = (a_m, b_m)（1 <= m <= n）将是最大的一对。如果我们想降低最大值，我们将不得不打破那对。但是我们可以 a_m 与谁配对，所以新配对的总和较小？我们需要找到一个低于 b_m 的 b，我们称它为 b_y（否则这不会是一个改进）。我们只能通过向上列表找到较低的 b_y，即 y < m。但同样适用于更上层的所有对：如果我们有更上层的一对（p_x 和 x < m）并尝试为旧的 a_x 找到一个新伙伴 b_y ，我们必须考虑 a_x >= a_m，这使得 y 的某些选择变得不可能。如果我们选择 y>=m，这意味着 b_y >= b_m，因此 quality(a_x, b_y) = a_x + b_y >= a_m + b_y >= a_m + b_m = quality(p_m)，这是我们想要避免的。所以 y 必须低于 m。如果我们考虑到该限制，a ({a_1,...,a_m}) 的 m 个可能值只有 m-1 个可能的伙伴 {b_1,...b_(m-1)}，因此配对是不可能的。因此，降低最佳配对的价值是不可能的。

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

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

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

Minimum difference between sum of two numbers in an array

c++

algorithm

optimization

dynamic-programming