网易补招笔试第二题想法,不知道对不对
网易12月9日补招。
第二题:小组赛之后剩下16只球队,共8个小组,每组的前2名。计算接下来可能的对阵方案数。
要求:
各小组的第一名不对战,各小组第二名不对战,同一小组的两只球队不对战,同一分区的两只球队不对战。
数据格式:
第一行数据组数
接下来每组数据占16行,每行格式为如"A1 ZN",A代表小组,1代表小组排名,ZN代表分区。
下面是我的解法(没来得及提交)。
通过这个程序计算出来的16只球队最多的对战方案数是 14833,不知道对不对。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 16
int ngroups;
char group[N][3]; // 用来存储球队所属小组与小组排名
char zone[N][3]; // 用来存储球队分区
int flag[N]; // 表示球队是否已分配对手
int sum = 0; // 多少只球队已分配对手
int check(int i)
{
// 能保证调用check(i)的时候,i之前的球队都已经分配对手
// 判断剩下的球队中对战方案数。
int ret = 0, j, tmp;
while(i<N && flag[i] != 0)
i+=1; // 查找从i开始没有对手的球队
flag[i] = i+1; // 方便打印调试用
sum += 1; // i 已分配
for(j=i+1;j<N; j++)
{
if(group[j][0]!=group[i][0] && group[j][1]!=group[i][1] && strcmp(zone[i], zone[j]) && flag[j] == 0)
{
flag[j] = i+1; // j可以作为i的对手
sum += 1;
if(sum==N)
{
// 判断是否所有球队都分配了对手, 如果是,则返回1
// for 语句用来调试
// for(tmp=0; tmp<N; tmp++)
// printf("%2d ", flag[tmp]);
// puts("");
ret = 1;
flag[j] = 0;
sum -= 1;
goto out;
}
// 有些球队还没有对手,从 i+1 开始查找没有配对的球队
ret += check(i+1);
flag[j] = 0;
sum -=1;
}
}
out:
flag[i] = 0;
sum -=1;
return ret;
}
int main()
{
int i;
scanf("%d", &ngroups);
while(ngroups--)
{
for(i=0; i<N; i++)
{
scanf("%s %s", group[i], zone[i]);
}
printf("%d", check(0));
}
return 0;
}
不知道对不对。