奥赛一本通 1432 糖果传递

1432 糖果传递题目大意给定一个环形正整数序列 $a_0, a_1, \dots, a_{n-1}$相邻的两个数可以传递数值代价就是数值大小求使每个数都相等的最小代价。知识要点贪心、绝对值解题思路将 $n$ 个数的平均值记为 $v$每个数向右传递的数值为 $x_i$ 负数则理解为 $(i1)$ 向左传递那么有 $a_i x_{i-1} - x_i v$于是 $x_i x_{i-1} a_i - v x_0 \sum_{k1}^i(a_i - v)$。如果记 $b_i \sum_{k1}^i(v - a_i)$最终的总代价为 $$|x_0| |x_1| |x_2| \dots |x_{n-1}| |x_0| |x_0 - b_1| |x_0 - b_2| \dots |x_0 - b_{n-1}| $$根据绝对值的意义当 $x_0$ 是数组 $b_i$ 的中位数时可以取得最小值。参考代码#includebits/stdc.husingnamespacestd;constintN1000005;longlonga[N],b[N],v,ans;intmain(){intn;scanf(%d,n);for(inti0;in;i)scanf(%lld,a[i]),va[i];v/n;for(inti1;in;i)b[i]b[i-1]v-a[i];nth_element(b,bn/2,bn);//取中位数for(inti0;in;i)ansabs(b[i]-b[n/2]);printf(%lld\n,ans);return0;}