题目链接:点击这里
此题刚开始做时没有什么思路,也不知道这么下手,但不可能穷举。由于对于任意一个人$x_i$,只可能向$x_{i-1}$或者$x_{i+1}$分金币,因此定义$x_i$为编号为$i$的人向编号为$i-1$的人给多少金币,如果$x_i<0$,则表示实际上是编号为$i-1$的人向编号为$i$的人$-x_i$个金币。
现假设有四个人1,2,3,4,编号为$i$的人初始有$A_i$个金币。对于1号来说,给了4号$x_1$个金币,2号给了他$x_2$个金币,因此还剩$A_1-x_1+x_2$个金币。而我们知道最后每个人的金币数量为平均数,记为$M$,因此我们得到方程:
$A_1-x_1+x_2 = M$
同理,我们可以对每个人列出方程,因此最终可以得到$n$个方程,一共有$n$个变量,但其实最后一个方程式无效的,实际上只有$n-1$个方程式有效的。
我们可以用$x_1$表示每一个变量,再通过$x_1$的极值解得出结果。例如:
$A_1-x_1+x_2 = M \to x_2 = M-A_1+x_1 = x_1 - C_1$
$A_2-x_2+x_3 = M \to x_3 = M-A_2+x_2 = x_1 - C_2$
读者可自行算出$C_i$,是一个递推公式,为:
$C_i = C{i-1} + A_i - M$
因此,我们希望所有的$x_i$的绝对值之和最小,即$|x_1| + |x_1 - C_1| +...+|x_1 - C_n-1|$的值要最小。可将这些点画在数轴上可得,其几何意义为未知数到$C_i$的距离总和最短。简单分析可得,当取值为中位数时,距离和最短。
由此可得,当输入点为奇数时,取中位数即可计算出结果,当输入点为偶数时,取最中间两个点之间的任意位置即可。
因此不难写出代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 10;
long long C[maxn],M,tot;
int main()
{
int n;
while (cin>>n)
{
tot = 0;
long long x = 0;
for (int i = 0; i < n; i++)
{
cin>>x;
tot += x;
C[i] = tot;
}
M = tot/n;
for (int i = 0; i < n;i++)
{
C[i] -= M*(i+1);\\递推计算
}
sort(C,C+n);
long long x1 = C[n/2],ans = 0;
for (int i =0; i < n; i++)
ans += abs(x1 - C[i]);
cout<<ans<<endl;
}
return 0;
}
需要注意的是,此题需要使用long long
类型才能AC。
网友评论