字节跳动青训营刷题笔记19

问题描述

小R正在组织一个比赛，比赛中有 n 支队伍参赛。比赛遵循以下独特的赛制：

• 如果当前队伍数为 偶数，那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛，且产生 n / 2 支队伍进入下一轮。
• 如果当前队伍数为 奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行 (n - 1) / 2 场比赛，且产生 (n - 1) / 2 + 1 支队伍进入下一轮。

小R想知道在比赛中进行的配对次数，直到决出唯一的获胜队伍为止。

测试样例

样例1：

输入：n = 7
输出：6

样例2：

输入：n = 14
输出：13

样例3：

输入：n = 1
输出：0

解题思路

比赛的规则如下：

1. 偶数队伍数：每两支队伍配对进行比赛，产生 n / 2 场比赛，剩下 n / 2 支队伍。
2. 奇数队伍数：有一支队伍轮空，剩下的队伍按 n - 1 个队伍进行配对，即 (n - 1) / 2 场比赛，最终晋级队伍数为 (n - 1) / 2 + 1 支。

每轮比赛都会进行配对，而每次配对的次数就是队伍数减半的过程。我们可以通过模拟比赛的过程，逐步减少队伍数，计算每一轮的配对次数。

详细步骤

1. 初始化：开始时队伍数为 n。
2. 循环处理：每一轮：
   • 如果队伍数为偶数：进行 n / 2 场比赛。
   • 如果队伍数为奇数：进行 (n - 1) / 2 场比赛，并且有一支队伍轮空晋级。
   • 更新队伍数：每轮晋级的队伍数为 (n + 1) / 2（即队伍数除以 2，并且如果是奇数还要加 1）。
3. 终止条件：当队伍数为 1 时，比赛结束，不再进行任何配对。

代码实现：

解释

1. 变量定义：

   • total_matches：记录总共进行的比赛次数。
   • n：当前队伍数。

2. 循环过程：

   • 每轮比赛中，如果 n 为偶数，则进行 n / 2 场比赛，并将 n 减半；
   • 如果 n 为奇数，则进行 (n - 1) / 2 场比赛，并且有一支队伍轮空，剩下的队伍数为 (n - 1) / 2 + 1。

3. 终止条件：当 n == 1 时，比赛结束，返回总配对次数。

复杂度分析

• 每次比赛都会减少一半的队伍数，因此时间复杂度为 O(log n)，其中 n 是初始的队伍数。

测试用例

1. 输入：n = 7

   • 7 支队伍，进行 3 场比赛，剩 4 支队伍。
   • 4 支队伍，进行 2 场比赛，剩 2 支队伍。
   • 2 支队伍，进行 1 场比赛，剩 1 支队伍。
   • 总配对次数：3 + 2 + 1 = 6

2. 输入：n = 14

   • 14 支队伍，进行 7 场比赛，剩 7 支队伍。
   • 7 支队伍，进行 3 场比赛，剩 4 支队伍。
   • 4 支队伍，进行 2 场比赛，剩 2 支队伍。
   • 2 支队伍，进行 1 场比赛，剩 1 支队伍。
   • 总配对次数：7 + 3 + 2 + 1 = 13

3. 输入：n = 1

   • 只有 1 支队伍，不需要进行任何比赛。
   • 总配对次数：0