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

Question

我试图解决这个问题:

物理学教授向班上的学生们提供了项目.学生必须组成一个由两人组成的团队来完成这个项目.教授让学生决定团队.班上的学生数量是均匀的.

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

学生决定组建团队,以便知识最高的团队与知识最低的团队之间的差异最小.

输入

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

产量

您的输出应该是一行,其中包含知识最高的团队与知识最低的团队之间的最低差异.

该解决方案归结为计算未排序数组中两个数之和的最小差异.到目前为止,我尝试过:

1. 对数组进行排序.
2. 在位置i和ni-1处添加元素,并将其与位置i + 1和ni处的元素之和进行绝对差异.
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_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，我们称其b_y为低于b_m（否则这不会是一个改进）。我们只能b_y通过向上查找列表来找到较低的，即y < m。但同样的情况也适用于所有更上面的对：如果我们有一对更上面的（p_x）并试图为旧x < m的 找到一个新的伙伴，我们必须考虑到这一点，这使得某些选择变得不可能。如果我们选择 a ，这意味着，因此我们想要避免。所以必须低于. 如果我们考虑到该限制，则( )的可能值只有可能的伙伴，因此配对是不可能的。因此，降低最佳配对的价值是不可能的。b_ya_xa_x >= a_myy>=mb_y >= b_mquality(a_x, b_y) = a_x + b_y >= a_m + b_y >= a_m + b_m = quality(p_m)ymma{a_1,...,a_m}m-1{b_1,...b_(m-1)}

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

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