问题描述

---

思路分析

1. 理解比赛规则

• 偶数队伍：如果当前队伍数为偶数，每两支队伍配对，比赛场次为 n / 2，进入下一轮的队伍数为 n / 2。
• 奇数队伍：如果当前队伍数为奇数，随机选择一支队伍轮空并直接晋级，其余队伍配对。比赛场次为 (n - 1) / 2，进入下一轮的队伍数为 (n - 1) / 2 + 1。

2. 目标

计算从 n 支队伍开始比赛，直到仅剩一支队伍的过程中，需要进行的 总配对次数。

3. 分析过程

我们可以通过一个循环模拟比赛过程：

1. 初始化总配对次数 totalMatches = 0。
2. 每轮比赛，计算当前的配对场次，并将其累加到 totalMatches。
3. 根据当前队伍数更新下一轮的队伍数：

• 偶数情况：n = n / 2。
• 奇数情况：n = (n - 1) / 2 + 1。

1. 重复上述过程，直到 n == 1（比赛结束）。

4. 时间复杂度

在每轮比赛中，队伍数大约减少一半，因此循环的次数为 O(log n)。每轮只进行简单的加法和除法操作，因此总的时间复杂度为 O(log n)。

---

参考代码（Java）

class Main {
    public static int solution(int n) {
        // 初始化配对次数
        int totalMatches = 0;

        // 循环进行比赛，直到仅剩一支队伍
        while (n > 1) {
            if (n % 2 == 0) {
                // 偶数情况：每两支队伍配对一次
                totalMatches += n / 2;
                n /= 2;
            } else {
                // 奇数情况：随机轮空一支队伍，其余队伍配对
                totalMatches += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }

        return totalMatches;
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution(7) == 6); 
        System.out.println(solution(14) == 13); 
        System.out.println(solution(1) == 0); 
    }
}

代码分析

1. 方法签名

public static int solution(int n) {

• 方法 solution 接受一个参数 n，表示参赛队伍的总数。
• 返回值是一个整数，表示整个比赛过程中所需的总配对次数。

2. 初始化变量

int totalMatches = 0;

• totalMatches 用于累计每轮比赛中产生的配对次数，初始值为 0。

3. 循环模拟比赛

while (n > 1) {

• 只要队伍总数 n 大于 1，就需要继续进行比赛。

4. 偶数队伍的处理

if (n % 2 == 0) {
    totalMatches += n / 2; // 当前轮的比赛场次
    n /= 2; // 下一轮的队伍数
}

• 如果队伍总数 n 是偶数：
• 配对场次为 n / 2，并将其累加到 totalMatches。
• 进入下一轮时，队伍总数直接减半。

5. 奇数队伍的处理

else {
    totalMatches += (n - 1) / 2; // 当前轮的比赛场次
    n = (n - 1) / 2 + 1; // 下一轮的队伍数（轮空一支队伍）
}

• 如果队伍总数 n 是奇数：
• 配对场次为 (n - 1) / 2，并将其累加到 totalMatches。
• 进入下一轮时，队伍数为 (n - 1) / 2 + 1，即 (n - 1) 支队伍参与配对，剩余 1 支队伍轮空直接晋级。

6. 返回结果

return totalMatches;

• 当 n == 1 时（即比赛结束，仅剩一支队伍），退出循环，返回累计的总配对次数。