企业官网建设流程全解析

1432 糖果传递

题目大意

给定一个环形正整数序列 $a_0, a_1, \dots, a_{n-1}$，相邻的两个数可以传递数值，代价就是数值大小，求使每个数都相等的最小代价。

知识要点

贪心、绝对值

解题思路

将 $n$ 个数的平均值记为 $v$，每个数向右传递的数值为 $x_i$ （负数则理解为 $(i+1)$ 向左传递），那么有 $a_i + x_{i-1} - x_i = v$，于是 $x_i = x_{i-1} + a_i - v = x_0 + \sum_{k=1}^i(a_i - v)$。如果记 $b_i = \sum_{k=1}^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$ 的中位数时可以取得最小值。

参考代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;longlonga[N],b[N],v,ans;intmain(){intn;scanf("%d",&n);for(inti=0;i<n;i++)scanf("%lld",&a[i]),v+=a[i];v/=n;for(inti=1;i<n;i++)b[i]=b[i-1]+v-a[i];nth_element(b,b+n/2,b+n);//取中位数for(inti=0;i<n;i++)ans+=abs(b[i]-b[n/2]);printf("%lld\n",ans);return0;}