4 条题解

  • 1
    @ 2026-9-24 12:01:36

    结论证明 :

    首先令 ai←ai−aˉa_i \leftarrow a_i - \bar a

    记每个 ii 移动到 i+1i+1 的纸牌个数为 xix_{i},若为负数则表示从i+1i+1移到ii。

    答案为 ∑i=1n∣xi∣\sum\limits_{i=1}^n |x_i| 的最小值。

    有方程组

    $$\begin{cases} x_n-x_1=a_1 \\ x_i-x_{i+1} =a_{i+1} ,i \in [1,n-1] \end{cases} $$

    我们发现这其实是一个差分的形式,我们改写一下:

    $$\begin{cases} x_n=a_1+x_1 \\ x_i =a_{i+1}+x_{i+1} ,i \in [1,n-1] \end{cases} $$

    若下面的那些方程成立,则 xn=a1+x1x_n=a_1+x_1 一定成立。

    记 Sx=∑i=xnaiS_x = \sum\limits_{i=x}^{n} a_i,则 ∀i∈[1,n−1],xi=Si+1+xn\forall i \in [1,n-1] , x_i=S_{i+1}+x_n。

    我们要使 ∑i=1n∣Si+xn∣\sum\limits_{i=1}^n |S_i+x_n| 最小,等价于找一个 xnx_n ,使得 ∑i=1n∣Si−(−xn)∣\sum\limits_{i=1}^n |S_i-(-x_n)| 最小。

    这是一个经典的问题,只需要让 −xn-x_n 成为 SiS_i 的中位数即可。

    • @ 2026-9-28 16:51:29

      式子是不是反了

      xn−x1=a1x_n - x_1 = a_1 改为 x1−xn=a1x_1 - x_n = a_1 ? 其余同理

信息

ID
82
时间
1000ms
内存
512MiB
难度
10
标签
(无)
递交数
202
已通过
6
上传者