Codeforces 13C解决方案

Question

http://codeforces.com/problemset/problem/13/C我在上面的问题上有问题。有人能清楚地解释这个解决方案吗？我的代码对我来说似乎还可以，但是它没有通过测试用例8。

lli n;
cin>>n;
lli arr[size];
fi(i,n)
cin>>arr[i];
if(n==1)
    cout<<"0"<<endl;
else
{
    lli sum=0;
    for(lli i=n-1; i>0; i--)
    {
        if(arr[i]<arr[i-1])
        {
            lli k=abs(arr[i]-arr[i-1]);
            if(i==(n-1))
            {
                arr[i]+=k;
                sum+=k;
            }
            else
            {
                if((arr[i]+k)<=arr[i+1])
                    arr[i]+=k, sum+=k;
                else
                    arr[i-1]-=k, sum+=k;
            }
        }
    }
    cout<<sum<<endl;
}

Answer 1

程序会比较arr[i]是否小于arr[i-1]，在10000 1 1 1这样的情况下可能会失败。

解决方案是O(n)，它将使每个数的平均值变为平均值。