UVa11300

题目链接

简介:
坐在圆桌边的n个人,没人有一定的金币,通过和身边人的交换,使得每个人手中的金币一样,求最少转移金币数目

分析:
这道题还是挺难的

我们需要慢慢分析
首先,我们可以算出来每个人最后手里的金币M(平均数)

假设有4个人,按顺序编号1,2,3,4
假设1号给2号3枚金币,2号给1号4枚金币,相当于2号给1号1枚金币,而1号没有给2号任何东西
那我们可以设x2表示2号给了1号多少枚金币
如果x2是负数,那么就代表1号给了2号金币
xi表示第i个人给第i-1个人的金币数目

现在假设第i个人有Ai枚金币,对于1号来说,ta给了4号x1枚金币(因为是环形的),2号又给了1号x2枚金币,
所以现在i号手里有A1-x1+x2
根据题目的要求,我们实际上得到了一个方程A1-x1+x2=M

这样我们就可以根据n个人得到n个方程,

然而

实际上最后一个方程我们可以通过前面的方程推导出来(因为是环形的)
所以我们现在只有n-1个方程是可用的

但是我们不虚,先画画柿子来看
我们可以用x1表示出其他的x

A1-x1+x2=M x2=x1+M-A1=x1-C1 (我们设Ci=Σ[1~i]{Ai-M})
A2-x2+x3=M x3=x1+M-A1+M-A2=x1-C2
A3-x3+x4=M x4=x1+M-A1+M-A2+M-A3=x1-C3

我们得到了xi=x1-C[i-1]

问题的终极目标是使所有xi的绝对值之和尽量少,即
|x1|+|x1-C1|+|x1-C2|+…+|x1-C[n-1]|
注意,|x1-Ci|表示的几何意义是Ci到x1的距离,问题就转变成了,数轴上有若干点Ci
找到一个离ta们距离之和最小的点(x1)

用我们的常识想想,我们就能想到,x1就是这(n-1)个数的中位数

对于ta的证明,那是非常的美妙和精巧

我们现在需要证明的是:

给定数轴上n个点,在数轴上所有点之中,中位数离所有定点的距离之和最小

凡是能转化成这个模型的题目都可以用中位数求解

让我们把题目具象化一下:
这里写图片描述
任意找一个点,如图中的红点,ta的左边有4个点,右边有2个点,
把ta往左移动一点,但是不碰到定点
假设我们移动了d的距离,总的来说距离之和就减少了2d
换句话说,如果红点两边的定点数目不同时,该点就不是最优点,那什么时候该点的两边有相等数目的点呢
当然是在中点

  • 输入点有奇数个,选中点就应该与中间的那个点重合(中位数)
  • 输入点有偶数个,选中点就可以位于最中间两个点之间的任意位置

tip

注意C的下标

//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

const int N=1000010;
int n;
ll C[N],a[N];

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        ll sum=0;
        for (int i=1;i<=n;i++) 
            scanf("%lld",&a[i]),sum+=a[i];
        sum/=n;                             //平均数         
        C[0]=0;
        for (int i=1;i<n;i++)
            C[i]=C[i-1]+a[i]-sum;           //xn=x1-C[n-1]
        sort(C,C+n);                        //一共n个元素 
        ll x1=C[n/2];
        ll ans=0;
        for (int i=0;i<n;i++) ans+=abs(x1-C[i]);
        printf("%lld
",ans);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/wutongtong3117/p/7673022.html