UVa 11300 分金币

https://vjudge.net/problem/UVA-11300

题意:

圆桌上有n个人,每个人都有一定的初始金币,每个人可以给他旁边的人一些金币,最终使每个人的金币数相等。计算最少需要转手的金币数量。

思路:
考数学。首先计算出平均金币数M,设每个人一开始的金币数为Ai。

我们设xi代表第i号给第i-1号的金币数量(x1代表第1号给最后1号的金币数量)。(如果是负的就说明是获得)

于是,我们可以列式计算:

1号:A1+x2-x1=M   —>     x2=M-A1+x1

2号:A2+x3-x2=M   —>     x3=M-A2+x2

3号:A3+x4-x3=M   —>     x4=M-A3+x3

因为最终我们是要计算出xi的和,那么:

x2=x1-C1   (C1=A1-M,下面类似)

x3=x1-C2

x4=x1-C3

接下来就是计算|x1|+|x1-C1|+|x1-C2|+...+|x1-Cn-1|的最小值,这就相当于给定数轴上的n个点,找出一个到它们的距离之和尽量小的点,这个点就是中位数。

 #include<iostream>
#include<algorithm>
using namespace std; const int maxn = + ;
int n;
long long a[maxn],c[maxn]; int main()
{
ios::sync_with_stdio(false);
//freopen("D:\\txt.txt", "r", stdin);
while (cin >> n)
{
long long sum = ;
for (int i = ; i <= n; i++)
{
cin >> a[i];
sum += a[i];
}
long long m = sum / n;
c[] = ;
for (int i = ; i < n; i++)
c[i] = c[i - ] + a[i] - m;
sort(c, c + n);
long long x1 = c[n / ], ans = ;
for (int i = ; i < n; i++)
ans += abs(x1 - c[i]);
cout << ans << endl;
}
}
上一篇:mysql5.7.18的安装与主从复制


下一篇:python学习02之线图表