笔试题 1.1 最少比赛数目

1, (from alibaba)宿舍内5个同学一起玩对战游戏,每场比赛有一些人作为红方,另一些人作为蓝方,请问至少需要多少场比赛,才能使任意两个人之间有一场红方对蓝方和一场蓝方对红方的比赛?

  对于这道题,如果使用穷举的方法,虽然是笨办法,但是不妨碍得到结果;因为题目规模很小,但是如果问题规模增大,例如是有N个学生,那么

此时的计算,我个人觉得应该是: 总计是需要比赛C(N,2)场次的, 但是如果要最少的比赛次数,那么每次分成两拨比赛方的时候,越是均匀划分,那么每场

比赛可以覆盖更多的比赛选手,所以分为 floor(N/2)和ceil(N/2)两拨,共有比赛floor(N/2) * ceil(N/2) 这么多长,假设需要比赛K场,那么应该有 

               K * ( floor(N/2) * ceil(N/2) ) >= C(N,2)

原文地址:https://www.cnblogs.com/superniaoren/p/3341083.html