列出比赛中的球员，这样每个球员都能战胜下一个选手？

Question

给定一个具有N people 的类(这由一个数组int[] a表示)，其中每个人都与所有其他人一起玩游戏。每场比赛将只涉及2名玩家。因此，对于N个人来说，将会有NC2游戏。

所有比赛的结果都和你在一起。你必须安排每个排队的人，条件是，ai应该在ai-1中获胜。对于i的所有值，THis都是正确的。

我们不需要关心ai和ai-2之间的结果。ai可以用ai-2赢得或输掉游戏.

我的方法(我使用回溯来解决这个问题)：

• 对于每个人，我们将保持一个名单，谁赢得了与该人的比赛。
• 将创建一个新的结果数组(长度等于玩家总数)。
• 第一个职位由每一个人轮流填补。
• 结果数组中的下一个位置由与前一个人一起赢得比赛的人填充。这个人将被从前面的人的相应的获胜列表中通过迭代那个数组来获得。

上面的解决方案将尝试使用递归方法的每一条路径。难道没有更好的算法吗？

Answer 1

以下是一个提示：

假设我们已经有了满足约束的第一个i-1人的排序。总能在某个地方把我的人插入这个名单吗？

考虑一下这些案例:要么是我打败了所有的第一个i-1人，要么是没有一个人，或者是他们中的一些人，但不是所有的人。在前两种情况下，我能被插入哪里？(这可能有助于为名单中的每个i-1人分配1或0，表明该人是否击败了I。)在第三种情况下，我们可以在他们殴打的任何人和任何殴打他们的人之间插入person I。这样的一对总是存在的吗？如果没有，是否还有其他地方保证我们能够安全地插入人员i？