⁴

【MarsCode】每日一题（模拟）之比赛配对问题

Cool

2024-11-09 22:16

阅读450

Cool

2024-11-09 22:16

阅读 450

比赛配对问题

1.问题描述

小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

2.思路与题解

配对次数的计算逻辑：
- 当前代码中，你在每次循环中更新 count 的方式可能有些问题。你需要确保每次配对的次数都被正确地累加。
- 对于偶数队伍数，配对次数应该是 n / 2，而不是 n。
- 对于奇数队伍数，配对次数应该是 (n - 1) / 2，而不是 (n - 1) / 2 + 1。
循环条件：
- 当前代码的循环条件是 n > 1，这是正确的，因为当 n 为 1 时，比赛已经结束。

Java

▼
java
复制代码
class Main {
    public static int solution(int n) {
        int count = 0; // 初始化配对次数
        
        // 当队伍数大于1时，继续进行配对
        while (n > 1) {
            // 如果队伍数为偶数
            if (n % 2 == 0) {
                // 进行 n / 2 场比赛
                n /= 2;
                count += n; // 更新配对次数
            } else {
                // 如果队伍数为奇数
                // 进行 (n - 1) / 2 场比赛，并有一支队伍轮空
                count += (n-1)/2;
                n = (n - 1) / 2 + 1;
            }
            
        }
        
        return count;
    }

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

C++

▼
c++
复制代码
#include <iostream>

int solution(int n) {
    int count = 0; // 初始化配对次数
    
    // 当队伍数大于1时，继续进行配对
    while (n > 1) {
        if (n % 2 == 0) {
            // 如果队伍数为偶数
            // 进行 n / 2 场比赛
            count += n / 2; // 更新配对次数
            n /= 2; // 更新队伍数
        } else {
            // 如果队伍数为奇数
            // 进行 (n - 1) / 2 场比赛，并有一支队伍轮空
            count += (n - 1) / 2; // 更新配对次数
            n = (n - 1) / 2 + 1; // 更新队伍数
        }
    }
    
    return count;
}

int main() {
    std::cout << (solution(7) == 6) << std::endl;
    std::cout << (solution(14) == 13) << std::endl;
    std::cout << (solution(1) == 0) << std::endl;
    return 0;
}

Python

▼
python
复制代码
def solution(n):
    count = 0  # 初始化配对次数
    
    # 当队伍数大于1时，继续进行配对
    while n > 1:
        if n % 2 == 0:
            # 如果队伍数为偶数
            # 进行 n / 2 场比赛
            count += n // 2  # 更新配对次数
            n //= 2  # 更新队伍数
        else:
            # 如果队伍数为奇数
            # 进行 (n - 1) / 2 场比赛，并有一支队伍轮空
            count += (n - 1) // 2  # 更新配对次数
            n = (n - 1) // 2 + 1  # 更新队伍数
    
    return count

print(solution(7) == 6)
print(solution(14) == 13)
print(solution(1) == 0)

Golang

▼
go
复制代码
package main

import "fmt"

func solution(n int) int {
    count := 0 // 初始化配对次数
    
    // 当队伍数大于1时，继续进行配对
    for n > 1 {
        if n%2 == 0 {
            // 如果队伍数为偶数
            // 进行 n / 2 场比赛
            count += n / 2 // 更新配对次数
            n /= 2 // 更新队伍数
        } else {
            // 如果队伍数为奇数
            // 进行 (n - 1) / 2 场比赛，并有一支队伍轮空
            count += (n - 1) / 2 // 更新配对次数
            n = (n - 1) / 2 + 1 // 更新队伍数
        }
    }
    
    return count
}

func main() {
    fmt.Println(solution(7) == 6)
    fmt.Println(solution(14) == 13)
    fmt.Println(solution(1) == 0)
}

2.5一些疑难的代码解释

偶数队伍数：
- count += n / 2;：每次配对次数应该是 n / 2。
- n /= 2;：更新队伍数为 n / 2。
奇数队伍数：
- count += (n - 1) / 2;：每次配对次数应该是 (n - 1) / 2。
- n = (n - 1) / 2 + 1;：更新队伍数为 (n - 1) / 2 + 1。