4 条题解
-
1
结论证明 :
首先令
记每个 移动到 的纸牌个数为 ,若为负数则表示从移到。
答案为 的最小值。
有方程组
$$\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} $$若下面的那些方程成立,则 一定成立。
记 ,则 。
我们要使 最小,等价于找一个 ,使得 最小。
这是一个经典的问题,只需要让 成为 的中位数即可。
信息
- ID
- 82
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 202
- 已通过
- 6
- 上传者