单循环无平局锦标赛最多获胜队伍数求解及代码问题咨询

N支队伍参与单循环无平局锦标赛（每支队伍与其他所有队伍各赛一场）。所有获胜场次不低于其他队伍的队伍被视为获胜队伍。求该锦标赛中最多能有多少支获胜队伍？

错误原因分析 #

你之前的代码错误在于对偶数N的情况判断偏差，误以为最多只有N/2支获胜队伍，但实际上偶数N时最多可达到N-1支，奇数N时最多能有N支。

正确解题思路 #

1. 奇数N的情况：

   • 当N为奇数时，每支队伍需进行N-1场比赛（偶数场）。可以构造循环赛制：让每支队伍恰好赢下(N-1)/2场，输掉另外(N-1)/2场。
   • 此时所有队伍胜场数完全相同，每支队伍的胜场均不低于其他队伍，因此全部N支队伍都能成为获胜队伍。
   • 例：N=3时，A胜B、B胜C、C胜A，每队各胜1场，全部属于获胜队伍。

2. 偶数N的情况：

   • 当N为偶数时，总胜场数为N*(N-1)/2，该数值无法被N整除（因N-1是奇数，(N-1)/2非整数），因此不可能让所有队伍胜场数相同。
   • 可构造这样的赛制：选出N-1支队伍，让这N-1支队伍内部形成奇数规模的循环（每队胜场相同），同时这N-1支队伍均赢下与剩余1支队伍的比赛。
   • 此时这N-1支队伍胜场数一致且均高于剩余队伍，因此这N-1支队伍都是获胜队伍。
   • 例：N=4时，A、B、C三队循环胜负（各胜1场），且都赢D，最终A、B、C各胜2场，D胜0场，这3支队伍均为获胜队伍。

正确代码实现 #

N = int(input())
if N == 1:
    print(1)
elif N % 2 == 1:
    print(N)
else:
    print(N - 1)

验证案例 #

• N=1：输出1，正确（唯一队伍自然是获胜队伍）。
• N=2：输出1，正确（仅获胜的那支队伍符合要求）。
• N=3：输出3，正确（三队循环胜负，胜场均为1）。
• N=4：输出3，正确（符合上述构造的赛制）。
• N=5：输出5，正确（五队内部循环，每队胜2场）。

内容的提问来源于stack exchange，提问作者Oleh Chyrkin