![[BZOJ1045] [HAOI2008] 糖果传递 (贪心) [BZOJ1045] [HAOI2008] 糖果传递 (贪心)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Description
有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
第一行一个正整数n<=,表示小朋友的个数.接下来n行,每行一个整数ai,表示第i个小朋友得到的
糖果的颗数.
Output
求使所有人获得均等糖果的最小代价。
Sample Input
1
2
5
4
Sample Output
HINT
Source
Solution
设$x[i]$表示$i+1$向$i$传的糖果数,$x[n]$表示$1$向$n$传的糖果数
$a[1]+x[1]-x[n]=\overline a$
$a[2]+x[2]-x[1]=\overline a$
$a[3]+x[3]-x[2]=\overline a$
$\cdots \cdots$
$a[n-1]+x[n-1]-x[n-2]=\overline a$
$a[n]+x[n]-x[n-1]=\overline a$(其实这个式子没用)
把式子变形:
$x[1]=\overline a-a[1]+x[n]$
$x[2]=\overline a-a[2]+x[1]=2*\overline a-a[2]-a[1]+x[n]$
$x[3]=\overline a-a[3]+x[2]=3*\overline a-a[3]-a[2]-a[1]+x[n]$
$\cdots \cdots$
$x[n-1]=\overline a-a[n-1]+x[n-2]=(n-1)*\overline a-\sum_{i=1}^{n-1}a[i]+x[n]$
$x[n]=n*\overline a-\sum_{i=1}^{n}a[i]+x[n]=0+x[n]$
设$\displaystyle s[i]=\sum_{j=1}^{i}a[j]-i*\overline a$,则:
$\displaystyle ans=\sum\mid x[i]\mid\ =\sum\mid s[i]-x[n]\ \mid$
所以当$x[n]$为$\big\{s[1], s[2], ..., s[n]\big\}$的中位数时答案最小
题面数据范围是在搞笑的,糖果数在$int$范围,答案在$long\ long$范围,剩下的就没什么难度了
#include <bits/stdc++.h>
using namespace std;
long long a[], s[];
int main()
{
int n;
long long ave = , ans = ;
scanf("%d", &n);
for(int i = ; i <= n; ++i)
scanf("%lld", a + i);
for(int i = ; i <= n; ++i)
ave += a[i];
ave /= n;
for(int i = ; i <= n; ++i)
s[i] = s[i - ] + a[i] - ave;
sort(s + , s + n + );
for(int i = ; i < n / + ; ++i)
ans += s[n / + ] - s[i];
for(int i = n / + ; i <= n; ++i)
ans += s[i] - s[n / + ];
printf("%lld\n", ans);
return ;
}
接下来是有爱的双倍经验时间:$BZOJ3293$