题目描述
有 \(n\) 个人和 \(k\) 个间隔相同时间的时刻，每个人都向正方向做匀速直线运动。给出每个时刻（\(0 \sim k - 1\)）的所有人的坐标集合（无序），在这 \(nk\) 个数中有一个数是错误的，找出这个错误的数并将其改正。
数据范围：\(5 \le n \le 1000\)，\(7 \le k \le 1000\)。
加强版：\(5 \le n \le 10^6\)，\(7 \le k \le 10^6\)。
solution
本题是一道人类智慧题，基本只有灵光一闪才能想出来。
我们可以考虑所有人的速度都是不变的，因此每个时间刻之间的坐标和之差是一定的。形式化的，我们可以写成下面的式子：
设 \(f_t=\sum \limits_{i=1}^n(x_i+v_it)\)，则
\[\begin{aligned}
f_{t+1} &= \sum \limits_{i = 1}^n(x_i+v_i(t+1))\\
&=\sum \limits_{i=1}^n(x_i+v_it)+\sum \limits_{i=1}^nv_i\\
&=f_t+\sum \limits_{i=1}^n v_i
\end{aligned}
\]
我们就可以用这个性质找到哪一列出现了问题。但是这无法定位到哪个数。因此我们需要再次动用人类智慧。
我们设 \(s_t=\sum \limits_{i=1}^n (x_i+v_it)^2\)。那么我们再次作差，展开就可以得到下面的式子：
\[s_{t+1}+s_{t-1}-2s_t=\sum \limits_{i=1}^n 2v_i^2
\]
然后枚举即可。
所以这题复杂度瓶颈在读入（？）
代码也是过于简单，不放了。