X

· · 题解

讲课的时候偶然发现的一道题。其他题解好麻烦啊！

首先思考:数轴上有一堆点上站着人。他们走到哪个点的路程和是最小的呢？

我们可以通过许多方法证明，应当取中位数。所以我们一定是想走到中央。

我们考虑，走 \leq 一步就能到中央的格子数目是 9，而走 \leq 两步就能到中央的格子数是 21。

但其实，走两步到中心点其实就是走一步到距离中心 = 一步的 8 个点再走一步而已。

据此我们可以 DP。设 f_i 表示走 \leqslant i 步就能到中心点的点数，那么 f_0=0。

f_i=f_{i-1}+((2\times i+1)\times 4-4)\times i

答案最后就是 f_{\lfloor\frac{n}{2}\rfloor}。

但其实展开就可以发现，答案就是自然数平方和的 8 倍的第 {\lfloor\frac{n}{2}\rfloor} 项。所以答案应该是：

\dfrac{{\lfloor\frac{n}{2}\rfloor}\times({\lfloor\frac{n}{2}\rfloor}+1)\times (2\times {\lfloor\frac{n}{2}\rfloor})+1}{6}

复杂度 O(T) 而不是 O(n+T)。

为了防止爆 long long 可以写成 ans = 1ll * (m + 1) * m / 2ll * (2ll * m + 1) / 3 ;