ICPC最大完美队伍数问题的超时解法优化求助

超时原因分析 #

你当前的代码采用逐次循环模拟组队扣减人数的实现方式，时间复杂度为O(n)。当题目输入的C、M、X数值达到10^8甚至更高量级时，循环需要执行上亿次运算，会直接触发时间超限。
这类计数类题目完全不需要模拟组队过程，通过分析约束条件直接用公式计算，就能把时间复杂度降到O(1)，不管输入数值多大都能瞬间出结果。

核心逻辑推导 #

每支符合要求的队伍必须同时满足三个硬性限制，最终能组建的最大队伍数就是这三个限制的最小值：

• 每队至少需要1名程序员，因此队伍总数不可能超过程序员总数C
• 每队至少需要1名数学家，因此队伍总数不可能超过数学家总数M
• 每队固定需要3名成员，因此队伍总数不可能超过三类学生总人数除以3的整数部分，也就是(C + M + X) // 3
  不管普通学生X的数量有多少，也不管C和M的差值有多大，最终结果一定不会突破这三个上限，取三者最小值就是正确答案。

优化后实现代码 #

c, m, x = map(int, input().split())
print(min(c, m, (c + m + x) // 3))

样例正确性校验 #

我们可以直接用你给出的三个测试样例验证：

• 样例1输入1 1 1：三个限制值分别为1、1、(1+1+1)//3=1，取最小得1，和样例输出一致
• 样例2输入3 6 0：三个限制值分别为3、6、(3+6+0)//3=3，取最小得3，和样例输出一致
• 样例3输入10 1 10：三个限制值分别为10、1、(10+1+10)//3=7，取最小得1，和样例输出一致
  其他边界场景也完全符合逻辑：比如C=5、M=5、X=0时，总人数10//3=3，min(5,5,3)=3，刚好可以组3队（2队按2程序员+1数学家配置，1队按1程序员+2数学家配置，刚好用完所有人员）。

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