[BZOJ1045][HAOI2008] 糖果传递[贪心,中位数]

题面

第一反应断环为链, 转化为均分纸牌, 但复杂度为$latex O(N^2)$根本不对. 实际上这道题比均分纸牌只多了1与n之间的转移, 设 n给1 $latex x_n$个糖果, i给i+1 $latex x_i$个糖果, 则有:

$$\left\{ \begin{array}{ll}
a_1+x_n-x_1=av \\
a_2+x_1-x_2=av \\
a_i+x_{i-1}-x_i=av \\
\end{array} \right.$$

所以有

$$\left\{ \begin{array}{ll}
x_1=a_1+x_n-av=S_1+x_n-1*av \\
x_2=a_2+x_1-av=S_2+x_n-2*av \\
x_i=a_i+x_{i-1}-av=S_i+x_n-i*av \\
\end{array} \right.$$

答案为

$$\sum x_i=\sum_{i=1}^{n} |S_i +x_n- i*av|$$

这个式子表示数轴上的一系列点到点$latex -x_n$的距离值和, 根据几何意义可知$latex -x_n$为所有$latex S_i – i*av $中位数时总代价最小.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址