BZOJ1045 糖果传递

题意简述:

有n个小朋友坐成一圈,每人有$a[i]$个糖果每人只能给左右两人传递糖果,每人每次传递一个糖果代价为1,求使所有人获得均等糖果的最小代价

输入格式:

第一行输入一个正整数$n$,表示小朋友的个数

接下来$n$行,每行一个整数$a[i]$,表示第$i$个小朋友初始得到的糖果的颗数

输出格式:

输出一个整数表示最小代价

数据范围:

$1\leq n\leq 1000000$

题解:

该题即为环形均分纸牌问题,是一道比较数学的题目

我们首先定义$a_{i}$为第$i$个人所有的糖果数,所有人糖果数之和为$sum$,不难发现题目若有解那么$\frac{sum}{n}$一定是整数,这样最后每个人的糖果数都要为$\frac{sum}{n}$,那么我们不妨实现先把$a$数组都减去$\frac{sum}{n}$,这样最后要使每个人糖果数都为0

接下来我们定义$x_{i}$为第$i$个人给第$i-1$个人的糖果数,正数即为$i$给$i-1$,负数即为$i-1$给$i$,特别的$x_{1}$表示第1个人给第$n$个人的糖果数,那么我们可以得到以下式子:

$a_{1}-x_{1}+x_{2}=0$

$a_{2}-x_{2}+x_{3}=0$

$a_{3}-x_{3}+x_{4}=0$

$\cdots\cdots\cdots\cdots\cdots$

$a_{n}-x_{n-1}+x_{1}=0$

总共有$n$个变量和$n$个未知数,理论上是可以用高斯消元之类的方法进行求解的,但实际上由前$n-1$个式子可以推出第$n$个式子,所以其实只有$n-1$个式子,但我们要求的是$\sum_{i=1}^n{x_{i}}$的最小值,那么我们可以把所有的$x$都用$x_{1}$来表示进行求解

由上面的式子不难整理出:

$x_{2}=x_{1}-a_{1}$

$x_{3}=x_{2}-a_{2}=(x_{1}-a_{1})-a_{2}=x_{1}-(a_{1}+a_{2})$

$x_{4}=x_{3}-a_{3}=\cdots =x_{1}-(a_{1}+a_{2}+a_{3})$

$\cdots\cdots\cdots\cdots\cdots$

通过这种类似于数学中累加的方式,我们可以得到公式:

$x_{n}=x_{1}-(a_{1}+a_{2}+\cdots +a_{n-1})$

不妨设$s_{n}=\sum_{i=1}^{n}{a_{i}}$

那么答案$\sum_{i=1}^n{x_{i}}=\mid x_{1}\mid+\mid x_{1}-s_{1}\mid+\mid x_{1}-s_{2}\mid+\cdots+\mid x_{1}-s_{n-1}\mid$

这样这道题就可以转化为货仓选址问题,即为在数轴上有$0,s_{1},s_{2}\cdots s_{n-1}$这$n$个点,我们要找到一个$x_{1}$使得到这$n$个货仓的距离最短,显然结论是$x_{1}$的取值为这$n$个数的中位数,那么这道题就解决了,只需要一次排序,时间复杂度为$O(n logn)$

AC代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1000050;
int n,a[maxn];
ll sum;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    sum/=n;
    for(int i=1;i<=n;i++) a[i]-=sum;
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
    sort(a+1,a+n+1);
    int mid=a[n+1>>1];
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=abs(a[i]-mid);
    cout<<ans<<endl;
    return 0;
}