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

Question

我正在努力解决这个问题

一位物理教授给班上的学生们做专题。学生们必须组成一个由两人组成的小组来做这个项目。教授让学生来决定队。一个班的学生人数是相等的。 每个学生都有一个知识水平。它告诉每个学生有多少知识。团队的知识水平是两个学生知识水平的总和。 学生们决定组成小组，这样知识最高的团队和知识最少的团队之间的差异是最小的。 输入 输入的第一行将包含测试用例的数量t；在后面的t行中，第一个数字是n，班级中的学生数，后面是表示n个学生知识水平的n个整数。 输出 您的输出应该是一条单行，包含知识最高的团队和知识最少的团队之间的最低可能差异。

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

1. 对数组进行排序。
2. 在位置i和n-i-1处添加元素，并将其绝对值与位置i+1和n处的元素之和相加。
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

首先，你是对的，迭代组合最好的剩余学生和最差的剩余学生给你最佳的结果(见下面的证明)。

但是，您没有正确计算该解决方案的成本。为了找到最好的和最差的组合的质量值，你必须遍历所有的组合，只有在找到它们之后，你才能减去它们的值。顺便说一句。不需要优先级队列来找到最小值(对于更复杂的用例，您可以多次插入和弹出，甚至更新队列中的值)，简单的累加器变量(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                   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，让我们把它称为比b_m低的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。如果考虑到这一限制，m可能值a ({a_1,...,a_m})只有m-1可能的合作伙伴{b_1,...b_(m-1)}，因此配对是不可能的。因此，降低最佳配对的价值是不可能的。

在上面的例子中:为了减少15的最大值，所有对的值都必须小于15，这意味着所有在最大对(8，8，9，10)以上或等于最大对(8，8，9，10)以上的对的左手边值都需要在最大对的右手边伙伴(7)以下的伙伴，所以只有1，4和5是可能的。

​

​

证明提高最坏对是不可能的证明同样适用于反向比较运算符和切换a和b (在这种情况下，对于太少的as，我们有太多的bs )。

Answer 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和1。

如果我们能填补最大的缺口，那就更好了，所以首先在左边。这样我们就得到了7和5的总和，这比平均水平稍差一些，但至少是1。任何其他配对都将是相同的或更糟的。

Answer 3

如果在对数组进行排序之后，开始从两端(第一个到最后等)添加值，只存储max和min结果，而不是队列，则会有所帮助。然后，你可以通过从最大值中减去min来得到答案。

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=1) so (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等进行扩展。如果一些值是相同的，那么替换将没有任何效果。