【题目】

【输入输出要求】

【输出样例】

【源代码】

<span style="font-family:Microsoft YaHei;font-size:24px;">//中位数问题
#include<stdio.h>
#include<algorithm>

int m[1000001],p[1000001];

int sub(int a,int b)
{
	if(a < b)
	{
		return b - a;
	}
	else
	{
		return a - b;
	}
}

int main()
{
    long long int n,Min,t;
    while(scanf("%lld",&n)!=EOF)//共n人
    {
       long long int  s=0;
        Min=0;
        for(long long int i=0;i<n;i++)//输入每个人的金币数
        {
            scanf("%d",&m[i]);
            s +=m[i];
        }

        t=s/n;//t为最终每人应该拿到的金币数
        p[0]=0;
        for(long long int i=1;i<n;i++)
        {
            p[i]=p[i-1]+m[i]-t;
        }

        std::sort(p,p+n);//进行从小到大排序

        long long int x=p[n/2];//取中位数

        for(long long int i=0;i<n;i++)//总转移的金币数目由每一个人与中位数的差的累积
            Min+=sub(x,p[i]);

        printf("%lld\n",Min);
    }
    return 0;
}</span>

m[i]-x[i]+x[i+1]=t，c[i]=m[i]-t;   x[i+1]=t-m[i]+x[i]=t-m[i]+(t-m[i-1]+x[i-1])=...=x[1]-c[i+1];将问题转化，表示此时我已经求出每个人要转移的数目为xi

如何使得所有的xi的和最小，即是|x[1]-c[i]|的和最小，每一个|x[1]-c[i]|表示一个点与点之间的距离之和最小
那么问题转化为求中位数的问题
  p[i]为|x1|,|x1-c1|,|x1-c2|,|x1-c3|,|x1-c4|,...,|x1-cn-1|中的ci值
找出一个点到各点距离之和最小