查看CodeForces/440B的源代码 ←CodeForces/440B

[[分类:模拟与排序]]
==摘要==
{{信息题| Balancer|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70537#problem/H|1|100|没用lld|1|time=2015-02-23 19:16:20}}
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70537 2015 Winter Warm up div1] H题
*原题链接：http://codeforces.com/problemset/problem/440/B
==题意==
n个火柴盒，每个火柴盒里有<m>a_i</m>根火柴，每次可以从一个火柴盒取出一根火柴到相邻的盒子去，问使得所有火柴盒数量相等的最少移动步数。
==题解==
目的是把每个火柴盒变成<m>\frac{a_1+a_2+...+a_n}{n}</m>根火柴，而向左移动m根火柴其实相当于向右移动-m根火柴，所以不用考虑左右。而顺序对结果也没有影响，所以就从最左边开始，依次利用每个火柴盒右边的火柴盒，将其火柴达到要求值即可。
（即使右边被移动成负数值也没有关系，等价地调一下顺序会补上的）
==代码==
{{折叠|440B.cpp代码已折叠
|<pre>
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<queue>
#include<vector>
using namespace std;
#define f(i,n) for(int i=1;i<=n;++i)
#define fi(i,t,n)for(int i=t;i<=n;++i)
#define fd(i,n) for(int i=n;i>=1;--i)
#define fdi(i,t,n) for(int i=n;i>=t;--i)
#define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i)
#define rforeach(i,s) for(typeof(s.rbegin()) i=s.rbegin();i!=s.rend();++i)
#define si(n) scanf("%d",&n)
#define dsi(n) int n;scanf("%d",&n)
#define llu unsigned long long
#define lld long long
#define ci const int &
long long n,a[50001],Ans=0,sum=0;//fixed:不能用int，不能用llu//
int main()
{
    cin>>n;
    f(i,n)
    {
        cin>>a[i];
        sum+=a[i];
    }
    f(i,n)
    {
        Ans+=abs(a[i]-sum/n);
        a[i+1]+=a[i]-sum/n;
    }
    cout<<Ans;
}
</pre>
|code440B}}