[bzoj1045] [洛谷P2512] [HAOI2008] 糖果传递

Description

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input

第一行一个正整数nn<=1'000'000，表示小朋友的个数． 接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．

Output

求使所有人获得均等糖果的最小代价。

Sample Input

4

1

2

5

4

Sample Output

4

---

想法

设第\(i\)个小朋友从他左边小朋友那里得到 \(l_i\) 个糖果，向他右边的小朋友传递 \(r_i\) 个糖果 （\(l_i\) 与 \(r_i\) 都可以为负数） 显然 \(l_i=r_{i-1}\) ,特殊地 \(l_1=r_n\) 设\(p\)为最终每个小朋友手中的糖果数 则有 \(l_i+a_i-r_i=p\) , 即 $ r_i=l_i+(a_i-p) $ 而我们又有 \(l_i=r_{i-1}\) 一直递归下去有 $ r_i=l_1+(a_1-p)+(a_2-p)+(a_3-p)+…+(a_i-p) $ 最终答案为 \(|r_1|+|r_2|+…+|r_n|\) 我们可以记下 \(a_i-p\) 的前缀和为 \(sum_i\) 那么 \(ans=|l_1+sum_1|+|l_1+sum_2|+…+|l_1+sum_n|\) 绝对值是个美妙的东西，\(|l_1+sum_i|\) 可想为数轴上 \(-l_i\) 与 \(sum_i\) 的距离 那么\(ans\)的最小值在 \(-l_1\) 取 \(sum_i\) 中位数时取到

求出\(sum_i\)及其中位数后计算即可。

---

代码

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N = 1000005; int a[N]; ll sum[N],p; int n; int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); p+=a[i]; } p=p/n; sum[0]=0; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-p; sort(sum+1,sum+1+n); ll l=sum[n/2+1],ans=0; //注意：中位数为n/2+1而不是n/2 for(int i=1;i<=n;i++) ans+=abs(sum[i]-l); printf("%lld\n",ans); return 0; }

转载于:https://www.cnblogs.com/lindalee/p/8455788.html

相关资源：数据结构—成绩单生成器