循环赛日程表问题

发表于 | 分类于 ， |
字数统计: 1,070 字 | 阅读时长 ≈ 5 分钟

$n=2^k$

当$n=2^k(k\in\lbrace 1, 2, 3\cdots,n\rbrace)$，$(n-1)$天比赛完，如下表当n=2时，我们在$2^{k-1}$行，$2^{k-1}$列处将表分割为四块，我们很容易看出，在一个最小块$(k=1)$中，只需将对角数值复制即可。然后将填完的块复制到对角的块，所以直接采用分治法解决问题。

例表

$\Rightarrow$ $n=2^k$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @author Swking
* @method circulateSchedule1
* @parame
*    int** table 二维数组，储存填写值
*    int n 运动员个数
* @return void
*/
void circulateSchedule1(int** table, int n){
    n /= 2; //对半分割数组
    if(n==0){
        table[1][1] = 1; //初始化
    }else{
        circulateSchedule1(table, n);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                //根据左上角，填写右上角
                table[i][j+n] = table[i][j] + n;
                //根据左上角，填写左下角
                table[i+n][j] = table[i][j] + n;
                //将左上角复制到右下角
                table[i+n][j+n] = table[i][j];
            }
        }
    }
}

$n\in\lbrace 1,\cdots,n\rbrace$

奇数时用$n$天，偶数时用$(n-1)$天

奇数时采用轮空规则，增加虚拟对手。
填写规则：
$\Rightarrow$当$n\%2=1$时：
$\rightarrow$ 从左上角1开始，往右下角对角处填1
$\rightarrow$ 在从1右边的2开始往右下角填写2，若数字相等（对手是自己）则轮空，填写0
$\rightarrow$ 若填到末尾列，但未填写末尾行时，将列转移到第一列的相同行继续往右下角填写

$\Rightarrow$当$n\%2=0$时：
$\rightarrow$ 和奇数填写规则一样，最后一行有BUG，但是不影响，我们可以先按规则填完，然后根据列来修正最后一行

例表一

$\Rightarrow$ $n\%2=1$

例表二

$\Rightarrow$ $n\%2=0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* @author Swking
* @method circulateSchedule2
* @parame
*    int** table 二维数组，储存填写值
*    int n 运动员个数
* @return void
*/
void circulateSchedule2(int** table, int n){
    for(int i=1; i<=n; i++){ //初始化第一列
        table[i][1] = i;
    }
    if(n%2==1){  //处理奇数的情况
        table[1][n+1] = 0;//奇数增加轮空位，值为0
        int temp;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                temp = (i+j-1) > (n+1) ? (i+j-1-n) : (i+j-1);
                if(j == table[i][1] && j != temp){  //当行数与第i行（除第1行）第一个数字相同，则该位置轮空，否则填写第i行的第一个数
                    //i+j-1>n+1?i+j-1%n:i+j-1 表示当前列大于最大列（超出范围）时，返回i+j-1-n列填写数字
                    table[j][temp] = 0;
                }else{
                    table[j][temp] = table[i][1];
                }
            }
        }
        printTable(table, n, n+1);
    }else{  //处理偶数的情况
        int temp;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                temp = (i+j-1) > n ? ((i+j)%n) : (i+j-1);
                if(j == table[i][1] && j != temp){
                    table[j][temp] = n;
                }else if(!(i==n && j==temp)){
                    table[j][temp] = table[i][1];
                }
            }
            //处理最后一行,每一列总和相等
            for(int i=2; i<n; i++){
                table[n][i] = (1+n)*n/2;
                for(int j=1; j<n; j++){
                    table[n][i] -= table[j][i];
                }
            }
        }
        printTable(table, n, n);
    }
}

无论奇偶都用$(n-1)$天

奇数时不轮空，不增加虚拟对手
填写规则：
$\rightarrow$ 以第一列为准，往右上角填写相同的数
$\rightarrow$ 若填到第一行，但未填写到末尾列时，将数字复制到末尾行的相同列继续往右上角填写

例表一

$\Rightarrow$ $n\%2=1$

例表二

$\Rightarrow$ $n\%2=0$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author Swking
* @method circulateSchedule3
* @parame
*    int** table 二维数组，储存填写值
*    int n 运动员个数
* @return void
*/
void circulateSchedule3(int** table, int n){
    for(int i=1; i<=n; i++){ //初始化第一列
        table[i][1] = i;
    }
    int temp;
    for(int i=1; i<=n; i++){
        for(int j=2; j<=n; j++){ //从第二列开始i，第一列已经初始化过了
            temp = (i-j+1+n) > n ? (i-j+1+n)%n : (i-j+1+n); //使得到达第一行后转换到最后一行
            table[temp][j] = table[i][1];
        }
    }
    printTable(table, n, n);
}

时间复杂度

我们只需要将二维数组填满即可，三种方法的时间复杂度都为

您的支持是我成长的动力！
0%