洛谷 P2512 [HAOI2008]糖果传递 题解
岸芷汀兰
2018-04-11 13:11:28
###作者：岸芷汀兰
#一、题目
[洛谷原题](https://www.luogu.org/problemnew/show/P2512)
#二、思路
**环形均分纸牌。**
没做过的可以做做[这道题](https://www.luogu.org/problemnew/show/P1031)
一般的均分纸牌问题就相当于在第N个人与第1个人之间把环断开，此时这N个人站成一行，其持有的纸牌数、前缀和分别是：
>A[1] S[1]
>A[2] S[2]
>…
>A[N] S[N]
如果在第K个人之后把环断开站成一行，这N个人持有的纸牌数、前缀和分别是：
>A[k+1] S[k+1]-S[k]
>A[k+1] S[k+2]-S[k]
>…
>A[N] S[N]-S[k]
>A[1] S[1]+S[N]-S[k]
>…
>A[k] S[k]+S[N]-S[k]
所以，所需最小花费为：$$\sum_{i=1}^{N}|S[i]-S[k]|$$
当K取何值时上式最小？这就是“货仓选址”问题。所以我们将S数组从小到大排序，取中位数作为S[k]就是最优解。
###三、代码
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline long long read(void)
{
long long x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=1000005;
long long n,a[maxn],sum[maxn],ave,ans;
int main()
{
n=read();
for(register int i=1;i<=n;i++){
a[i]=read();ave+=a[i];
}
ave/=n;
for(register int i=1;i<=n;i++)a[i]-=ave;
for(register int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
sort(sum+1,sum+n+1);
long long t=sum[(n+1)>>1];
for(register int i=1;i<=n;i++)ans+=abs(t-sum[i]);
printf("%lld\n",ans);
return 0;
}
```