java - 在不使用结构的情况下冒泡某种条件？

Question

有一场比赛。玩家由整数标识，并以与他们相邻的整数进行比赛的方式进行比赛。所以，1 玩 2，3 玩 4，5 玩 6，7 玩 8。然后，1/2 玩 3/4，5/6 玩 7/8，然后 1/2/3/4 玩 5/6/7/8。

示例输入:

8 5
1 2 3 4 5

第一行 = 第一个数字是参加锦标赛的玩家人数(总是一些 2^N 个数字)，第二个数字是在锦标赛开始前退出的玩家人数

第二行=退出的玩家ID

如果玩家自动晋级到下一轮，因为他们本应玩的人退出(称为 BYE)，则增加计数。最后输出计数。

因此样本输入的输出为 2(第一轮 6 自动晋级，因为 6 本应与退出的 5 比赛，最终在倒数第二轮中，6/7/8 自动晋级) .

我正在考虑要么将所有内容都保存在树中(但这真的不会很有效，对吗？)，或者只是边走边解析，然后冒泡 BYE。第二种解决方案的问题是我不知道如何根据谁将扮演谁来考虑/存储关系，以及在实现中如何在没有结构的情况下冒泡一些东西。

Answer 1

您可以使用一个简单的数组(大小为 2^N)。将您的参与者编码为 0 表示缺席，1 表示出席，并模拟锦标赛。在每一轮中，索引为 2*k 的玩家再次与索引为 2*k + 1 的玩家对战，“获胜者”移至索引为 k。再见条件是异或，“赢家”是或。在伪代码中，

    while player_count > 1
        for k in range (player_count / 2)
            byes += arr[2*k] ^ arr[2*k + 1]
            arr[k] = arr[2*k] | arr[2*k + 1]
        player_count /= 2

空间和时间都与玩家数量呈线性关系。