C语言实现2^k人锦标赛：求每人获胜场次的高效方案咨询

问题说明 #

• 参与人数为 (2^k)（(k) 由用户输入）
• 每位参与者分配0到 (2×10^7) 范围内的数字（用户输入）
• 共进行 (k) 轮比赛：
  • 每轮相邻两人对决，胜负规则：若两人数字差的绝对值能被2整除，则前者获胜；否则后者获胜
  • 胜者晋级下一轮，直至最后一轮结束
• 输出每位参与者的获胜场次

示例：
k=2，共4位参与者，数字为6、2、3、4。6与2对决，6获胜；3与4对决，4获胜；6与4对决，6获胜。输出结果为2 0 0 1。

高效实现思路 #

不需要纠结动态调整数组的复杂操作，用双数组模拟晋级过程即可，逻辑直观且性能足够应对大部分场景（即使k=20，对应100万+参与者也能轻松处理）。

核心逻辑 #

用两个数组分别存储当前轮次的选手信息和下一轮的晋级选手，每轮结束后切换数组（或动态分配内存释放旧数组），同时维护一个胜场计数数组记录每个原始选手的获胜次数。

完整代码实现 #

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int num;
    int idx; // 记录原始索引，用于更新胜场计数
} Player;

int main() {
    int k;
    printf("输入k值: ");
    scanf("%d", &k);
    int total_players = 1 << k; // 计算2^k
    
    // 初始化胜场计数数组，默认全0
    int* win_count = calloc(total_players, sizeof(int));
    // 初始化当前轮次选手数组
    Player* current_round = malloc(total_players * sizeof(Player));
    
    printf("输入%d个数字: ", total_players);
    for (int i = 0; i < total_players; i++) {
        scanf("%d", &current_round[i].num);
        current_round[i].idx = i;
    }
    
    // 进行k轮比赛
    for (int round = 0; round < k; round++) {
        int curr_size = total_players >> round;
        int next_size = curr_size / 2;
        Player* next_round = malloc(next_size * sizeof(Player));
        
        // 两两对决，选出晋级者
        for (int i = 0; i < curr_size; i += 2) {
            Player p1 = current_round[i];
            Player p2 = current_round[i+1];
            
            if (abs(p1.num - p2.num) % 2 == 0) {
                win_count[p1.idx]++;
                next_round[i/2] = p1;
            } else {
                win_count[p2.idx]++;
                next_round[i/2] = p2;
            }
        }
        
        // 释放当前轮数组，切换到下一轮
        free(current_round);
        current_round = next_round;
    }
    
    // 输出结果
    printf("获胜场次结果: ");
    for (int i = 0; i < total_players; i++) {
        printf("%d ", win_count[i]);
    }
    printf("\n");
    
    // 释放剩余内存
    free(current_round);
    free(win_count);
    return 0;
}

优化点说明 #

1. 动态内存管理：每轮结束后释放当前轮的数组，避免内存浪费，同时适配任意k值的人数需求。
2. 原始索引跟踪：通过结构体存储选手的原始索引，确保胜场计数能准确对应到初始输入的选手顺序。
3. 位运算简化计算：用 1 << k 计算总人数，total_players >> round 计算当前轮次的参赛人数，比乘法除法更高效。

内容的提问来源于stack exchange，提问作者Wow1345