大疆校招测评题--循环赛问题

笔者在2022.7参加了大疆的测评题。

其中有道循环赛问题，记录下解题思路。

循环赛问题

六名选手A, B, C, D, E, F进行循环赛。

每两名选手间比赛一次，每名选手每天比赛一场。

五天内完成循环赛。

已知：

        第一天C赢了F，

        第二天A赢了B，

        第三天C败给D，

        第四天A赢了F，D败给E

求：这五天的赛程安排。

 解题思路

        “每名选手每天比赛一场”，说明一天内ABCDEF都有比赛，总共三场比赛，只是对手组合不同。比如[AB，CD，EF]是一种情况，[AC，BE，DF]是另外一种情况。

        “每两名选手间比赛一次”，比如出现了AB，那么剩下的赛程里肯定没有AB。

        这两点，类似数独中，每行都要有1~9，但同一行中不能有重复数字。可以用数独的思路做。

解题步骤

        题目已知条件构建初始状态：(CF表示C与F的比赛)

        因为第四天已经有ADEF的比赛了，那么剩下一场比赛一定是BC，填入表格：   

        接下来看第三天的比赛，CD已有比赛，则从ABEF中安排两场比赛。因为AB，AF已存在，则A只能跟E打比赛，即AE，剩下一场为BF，填入表格：

        同理，推导出第二天的赛程为CE，DF，第一天的赛程为AD，BE：

        还未两两比赛的组合AC，BD，EF，填到第五天，得到最终的赛程表：

        问题求解完成。