唯一对的算法分组列表

Question

我收到的作业有困难，我很确定问题的文本是有缺陷的。我把它翻译成：

---

考虑一个列表x[1..2n]，其中元素来自{1,2，…，m}，m<；n。在Python中提出并实现一个复杂度为O（n）的算法，该算法将元素分组为成对的（成对的（x[i]，x[j]），例如每个元素都存在于单个对中。对于每一组对，计算这些对的最大和，然后将其与其余组进行比较。返回具有最小值的集合。在

For example, x = [1,5,9,3] can be paired in three ways:
(1,5),(9,3) => Sums: 6, 12 => Maximum 12
(1,9),(5,3) => Sums: 10, 8 => Maximum 10
(1,3),(5,9) => Sums: 4, 14 => Maximum 14
                              ----------
                              Minimum 10
Solution to be returned: (1,9),(5,3)

---

让我感到奇怪的是：

• 表内容定义它表示有1..2n, from {1..m}, m < n的元素。但是如果m < n，那么没有足够的元素来填充列表而不复制一些元素，这是不允许的。所以我假设m >= 2n。另外，这个例子有n = 2，但是使用了大于1的元素，所以我假设这就是它们的意思。

• O（n）复杂性？那么有没有办法在一个循环中组合它们？我什么都想不出来。

---

我的计算：

^{pr2}$

所以很明显，我不能使用暴力，然后再弄清楚它是否有效。我用来计算所有可能的方法的公式是

C(C(n,2),n/2)

---

问题：

这个问题写错了，不可能解决吗？如果是这样的话，应该增加或取消哪些条件使之可行？如果您要建议使用python编写一些代码，请记住我不能使用任何类型的预构建函数。谢谢你

Answer 1

假设一个已排序的列表：

def answer(L):
    return list(zip(L[:len(L)//2], L[len(L)//2:][::-1]))

或者，如果您想手动操作：

^{pr2}$

输出：

In [3]: answer([1,3,5,9])
Out[3]: [(1, 9), (3, 5)]