题解 P2512 【[HAOI2008]糖果传递】

2018-11-29 22:16:02


其它大佬都太强了,写的题解我都看不懂qwq

结果还是问了ych才搞懂的qwq

于是来发一个自我感觉写的好的题解。


尝试手推一遍过程。

首先,要让每个孩子的糖果数都变为

$$\Large\overline{a}=\frac{\sum\limits_{i=1}^{n}a_i}{n}$$

和均分纸牌一样,设 $x_i$ 表示给上一个人的糖果数,正数就是给,负数就是拿。

这里传给编号大的人后面会不好推,所以选择传给编号小的那个人。

然后传递后第 $i$ 个人的糖果数 $b_i$ 就是:

$$\Large b_i=a_i+x_{next}-x_{i}$$

显然 $\forall b_i,b_i=\overline{a}$ 。

然后就可以列方程组:

$$\Large\begin{cases}a_1+x_2-x_1=\overline{a}\\a_2+x_3-x_2=\overline{a}\\......\\a_n+x_{1}-x_n=\overline{a}\end{cases}$$

发现这个方程组解不出,所以用 $x_1$ 来表示 $x_i(i\neq 1)$ 。

容易得到:

$$\Large\begin{cases}x_2=\overline{a}-a_1+x_1\\x_3=\overline{a}-a_2+x_2\\......\\x_{n}=\overline{a}-a_{n-1}+x_{n-1}\end{cases}$$

然后再化简,得到:

$$\Large x_i=x_1+\sum\limits_{j=1}^{i-1}\ \overline{a}-a_j\quad(2\leq i\leq n)$$

定义:

$$\Large c_i=\begin{cases}0&i=1\\\sum\limits_{j=1}^{i-1}\ a_j-\overline{a}&2\leq i \leq n\end{cases}$$

然后就变成了:

$$\Large x_i=x_1-c_{i}$$

试着写出答案:

$$\Large ans=\sum\limits_{i=1}^{n}\ |x_i|\Rightarrow ans=\sum\limits_{i=1}^{n}\ |x_1-c_i|$$

我们要取一个 $x_1$ ,使得 $ans$ 最小。易证 $x_1$ 取 $c_m\ (m=\left\lceil \frac{n}{2} \right\rceil)$ 时 $ans$ 最小。


具体实现见代码,如有错误请私信我qwq