[LOJ10010]糖果传递


\(设x_{i}为第i个同学从第i-1个同学获得的糖果数,若x_{i} < 0,则第i-1个同学从第i个同学获得-x_{i}个糖果\)

\(特别地,x_{1}为第1个同学从第n个同学获得的糖果数\)

\(均分后,每个同学拥有的糖果为avg = \frac{\sum_{i = 1}^{n}a_{i}}{n},则\)

$$avg = a_{1}+x_{1}-x_{2} \\ avg = a_{2}+x_{2}-x_{3} \\ … \\ avg = a_{n}+x_{n}-x_{1}$$

\(改写一下,有\)

$$x_{2} = avg-a_{1}+x_{1} \\ x_{3} = avg-a_{2}+x_{2} = 2avg-a_{1}-a_{2}+x_{1} \\ … $$

\(记c_{i}=\sum_{j=1}^{i}a_{j}-iavg,则有\)

$$x_{i} = x_{1}-c_{i}$$

\(问题所求的代价则为\sum_{i=1}^{n}|x_{1}-c_{i}|,要使其最小,则x_{1}为c_{i}的中位数\)

\(用STL中的nth_element()求中位数,复杂度O(n)\)


 

发表评论