网易补招笔试第二题想法,不知道对不对

网易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;
}   
不知道对不对。

#网易#
全部评论
全排列就行了啊横竖就8层
点赞 回复 分享
发布于 2017-12-09 17:27
ac了吗?
点赞 回复 分享
发布于 2017-12-09 13:58
3道题 交的白卷23333333
点赞 回复 分享
发布于 2017-12-09 15:58
直接暴力就可以了吧。。。数据这么小
点赞 回复 分享
发布于 2017-12-09 16:59
6
点赞 回复 分享
发布于 2017-12-12 16:51

相关推荐

11-01 20:03
已编辑
门头沟学院 算法工程师
Amazarashi66:这种也是幸存者偏差了,拿不到这个价的才是大多数
点赞 评论 收藏
分享
面试摇了我吧:啊哈哈面试提前五个小时发,点击不能参加就是放弃
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务