输入是实数序列 x1, x2, ..., x2n。我们想将这些数字配对成 n 对。对于第 i 对 (i = 1, 2, ..., n)，令 Si 表示该对中数字的总和。 (例如，如果将 x(2i−1) 和 x2i 作为第 i 对配对，则 Si = x(2i−1) + x2i)。我们想对这些数字进行配对，以使 Maxi[Si] 最小化。设计一个贪心算法来解决这个问题 问题。
就是这个问题；我的解决方案是简单地对数字进行排序并将第一个元素与最后一个元素配对并加一/减一索引并重复。该算法会尝试针对每一对进行优化，使其变得贪婪。我只是想知道是否有线性时间算法可以做到这一点？
PS:这不是作业，但我知道这看起来很像。
最佳答案
没有。不可能有线性时间算法来为您完成这项工作。输入的数字可以按任何顺序排列，因此您无法使用 min Maxi[Si] 立即完成配对。您当前的解决方案既简单又好。
改进运行时间的建议:
您可以根据输入的数字创建二叉树(这需要 O(nlog(n)) 时间)。对树进行有序遍历并从 (first+i, last-i) 个元素(i 从 0 到 n/2)创建对
关于algorithm - 配对数字的贪心算法使最大和最小化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10003739/