1.题目描述：点击打开链接
2.解题思路：本题要求若干个人分金币时交换的最少金币数。由于最后每个人获得的金币数量一样，即平均值M，那么我们可以设出来第i个人传递给第i+1个人的金币数量是Xi（把队列当做循环的），那么每个人都可以看做一个结点，根据结点可以列写相应的转移方程：Ai+X(i-1)-X(i)=M。整理后发现，，每个Xi都等于X1-|Ai-M|，令Ci=|Ai-M|,所以本题就是求sum{|x1-Ci|}的最小值。显然当x1是所有Ci的中位数时，这个值最小。由此不难写出代码。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 1000000+10typedef long long LL;LL a[N], c[N], tot, M;int main(){//freopen("t.txt", "r", stdin);int n;while (scanf("%d", &n) == 1){tot = 0;for (int i = 1; i <= n; i++){cin >> a[i];tot += a[i];}M = tot / n;//M是平均值c[0] = 0;for (int i = 1; i < n; i++)//递推求解Cic[i] = c[i – 1] + a[i] – M;sort(c, c + n);LL x1 = c[n / 2], ans = 0;//x1是所有Ci的中位数for (int i = 0; i < n; i++)ans += abs(x1 – c[i]);cout << ans << endl;}return 0;}
却又小到连一粒嫉妒的沙石也不能容纳
