uva11300 - Spreading the Wealth(分金币)

本文主要是介绍uva11300 - Spreading the Wealth(分金币)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代数分析：：：：

先算出平均数ave然后我们开始分析，，，，

每个人都只有给出和给进两部分，如果用数字表示则是一负一正

1号座位的人只与4号和2号有联系，则有x1表示1给4的，同理x2表示2给1的。

如果x1<0则表示4给1了-x1个金币。。

1： A1-x1+x2=ave -> x2 = ave-A1+x1 = x1-C1(C为常数)

2： A2-x2+x3=ave -> x3 = ave-A2+x2 = ave-A2+x1-C1=x1-C2

3： A3-x3+x4=ave -> x4 = ave-A3+x3 = ave-A3+x1-C2=x1-C3

.....

n: An-xn+x1=ave -> xn = ave-An+x1 = ave-An+x(n-1)=x1-Cn

我们的目的要求|x1|+|x1-C1|+|x1-C2|+...|xn-Cn|的最小值，

我们可以把上式看作要求点x1使得x1到0，C1，C2....Cn的距离最短。

然后求出最小值就行了。这就是代数分析。

很实用的能把题目难度降低的思路之一。。。。

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
#define M 1000010
long long a[M], c[M];
int main ()
{long long n, sum, ave;while(scanf("%lld",&n)==1){sum = 0;for(int i = 1; i <= n; i++) {scanf("%lld",&a[i]); sum+=a[i];}ave = sum/n; c[0] = 1;for(int i = 1; i <= n; i++) c[i] = c[i-1]+a[i]-ave;sort(c,c+n);long long x1 = c[n/2], ans = 0;for(int i = 0; i < n; i++) ans+=abs(x1-c[i]);printf("%lld\n",ans);}return 0;
}

这篇关于uva11300 - Spreading the Wealth(分金币)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---