题目解析

本题需要找到与给定统计数据不矛盾的最小玩家人数。已知每栋建筑举办的对局数，且每场对局需要三名玩家，对局地点由玩家所在建筑决定：

• 如果两名玩家在同一建筑 (x)，则对局在 (x) 举行。
• 否则，对局在三个玩家建筑编号的中位数建筑举行。

关键点在于：实际对局数不一定需要恰好等于给定数据，但必须确保每个建筑举办的对局数至少达到给定值 (a_i)。同时，总对局数不能超过可能的三元组数量 (C(m, 3))，其中 (m) 是玩家人数。

算法思路

1. 二分答案：在可能玩家人数范围内进行二分查找。玩家人数下界为 3（至少需要3人进行一场对局），上界设为 200008（根据数据范围设定）。
2. 验证函数：对于候选玩家人数 (x)，检查是否存在一种玩家分配到建筑的方案，使得每个建筑 (i) 举办的对局数至少为 (a_i)。
   • 使用贪心策略按建筑编号顺序分配玩家。
   • 对于建筑 (i)，计算需要分配的最小玩家数 (cur)，使得对局数满足： [ \binom{cur}{3} + \binom{cur}{2} \cdot (x - cur) + left \cdot cur \cdot (x - left - cur) \geq a_i ] 其中：
     • (\binom{cur}{3})：三个玩家都在建筑 (i) 的对局数。
     • (\binom{cur}{2} \cdot (x - cur))：两个玩家在建筑 (i)、一个玩家在其他建筑的对局数。
     • (left \cdot cur \cdot (x - left - cur))：一个玩家在建筑 (i)、一个玩家在编号小于 (i) 的建筑、一个玩家在编号大于 (i) 的建筑，且建筑 (i) 是中位数的对局数。
   • (left) 是前 (i-1) 个建筑累计玩家数。
   • 如果分配过程中总玩家数超过 (x)，则验证失败。
3. 输出结果：找到满足验证的最小玩家人数。

复杂度分析

• 二分查找次数为 (O(\log 200008) \approx O(18))。
• 验证函数需要 (O(n)) 时间，其中 (n) 是建筑数量。
• 总复杂度为 (O(t \cdot n \cdot \log 200008))，在题目约束下（(n) 总和不超过 200000）可接受。

该方法通过二分搜索快速确定最小玩家人数，并利用贪心分配和组合公式高效验证可行性，确保在大量数据下也能快速求解。