由于本题有各种简化的条件：
1.是n的倍数
2.只能从左右移过来

所以显然只需要从左到右走一遍就好了
显然是最优解

#include<bits/stdc++.h>
using namespace std;
int n;
int a[101];
int main()
{

    cin>>n;
    int sum=0;
    for(int  i=1;i<=n;i++)
    cin>>a[i],sum+=a[i];
    int ave=sum/n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>ave) a[i+1]+=a[i]-ave,a[i]=ave,ans++;
        if(a[i]<ave) a[i+1]-=ave-a[i],a[i]=ave,ans++;
    }
    cout<<ans;
return 0;
}

顺便吐槽一下vijos的评测太水了。一开始写错了一个字符名字竟然都过了

求赞<
求顶<
谢谢<

/*
炒鸡经典的贪心了吧
题目着重说明纸牌总数是n的倍数是有意图的= =
对于一组牌
我们直接先求出平均值来
然后每堆牌都减去这个平均值
就会出现有正有负数
然后我们就相当于要怎么移动这些数
让它们最后和为0
QAQ我们可以想到负数其实也是可以移动的
因为我们将一个负数从左移动到右边
就相当于将一个正数(多余的牌)从右移动到左
等效的只是为了更好理解
然后我们就贪心吧
不用说就像模拟一样
考虑到每一堆牌
就直接不断移到右边使自己变成0就好了
即
为了使每堆纸牌一样多，总和上面的条件，最好的情况当然是每堆都是平均数
然后利用差分思想，ci表示第i堆纸牌数-平均数
由于开头和结尾只能向右传递，所以我们可以贪心的认为每张纸牌都向右传递
ci就利用到了，如果ci没有摆好，那就给后面的纸牌，记录一次
然后就直接解决了
So easy~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int a[102];
int n,sum=0;

int main()
{
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum+=a[i];
    int tot=sum/n;
    for(int i=1;i<=n;i++)
        a[i]-=tot;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=0)
        {
            a[i+1]+=a[i];
            ans++;
            a[i]=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}
     

贪心

#include<iostream>

using namespace std;

const int MAXN = 105;
int a[MAXN], n, ans, sum, cri;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    cri = sum / n;
    for(int i = 1; i <= n; i++){
        if(a[i] == cri) continue;
        a[i+1] -= cri-a[i];
        ans++;
    }
    cout << ans;
    return 0;
}

Pascal AC
var n,i,k,s:longint;
a:array[1..100]of longint;
begin
readln(n);
s:=0;
for i:=1 to n do
begin
read(a[i]);
s:=s+a[i];
end;
s:=s div n;
k:=0;
for i:=1 to n-1 do
if a[i]<>s then
begin
a[i+1]:=a[i]-s+a[i+1];
a[i]:=s;
inc(k);
end;
write(k);
end.

#include<bits/stdc++.h>
using namespace std;
const int N=209;
int n,ans,s[N],a[N];
int main(){
// freopen("cards.in","r",stdin);
// freopen("cards.out","w",stdout);
cin>>n;//输入排堆数
for(int i=1;i<=n;i++)
cin>>a[i];//输入数字
for(int i=1;i<=n;i++)//前缀和
s[i]=s[i-1]+a[i];
int avg=s[n]/n;//定义平均值
for(int i=1;i<=n-1;i++)
if(s[i]!=avg*i)//不管多少
ans++;//答案++
cout<<ans<<endl;
return 0;
}

#include <iostream>  
using namespace std;  
int main()  
{ 
int a,p=0,js=0; cin >>a;int q[a];  
for (int y=0;y<a;y++){cin >>q[y]; p+=q[y];} p/=a;  
for (int y=0;y<a;y++)q[y]-=p;  
for (int y=0;y<a;y++) {if (q[y]==0)continue; q[y+1]+=q[y]; js++; }  
cout <<js;  
return 0;
}  

/*Tokgo*/
/*
经典精妙的贪心法
不用管操作顺序，只问次数
我们从特殊情况入手
发现最左侧的纸牌a[i]!=avr的情况一定要和其右侧纸牌i+1交互
交互完了之后a[i]与avr的差异转到了a[i+1]上
这样问题规模就缩小了
我们就可以不断贪心得到最优解了
*/
#include <iostream>
#include <vector>
using namespace std;
int a[101];
int avr;
int ans;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        avr+=a[i];
    }
    avr/=n;
    for(int i=1;i<=n-1;++i){
        if(a[i]!=avr){
            ++ans; 
            a[i+1]+=(a[i]-avr);
        }
    }
    cout<<ans;
    return 0;
}

题解：递归解法
* 我们知道最后一堆要想达到目标状态，只能与前一堆发生关系（？）或一开始就是目标状态
* 我们假设要发生关系，那么想前一堆与它的后一堆都达到目标状态则前一堆的目标状态就需要改变。
* 总而言之就是对于每一堆需要达到的目标状态都有属于自己的与他堆不一样的值。而达到这个值与其前一堆有关。

举个栗子：甲堆=9、乙堆=8、丙堆=17、丁堆=6；

丁堆目标状态是10，只能由丙堆拿过来，那么丙堆的目标状态变成10+（10-6）=14；加一次ans；
这里加ans是丙给丁的过程，那么丙就一定不能从丁那儿拿，相当于丙变成了最后一堆；

丙堆目标状态是14，只能由乙堆拿过来，不过丙已经是17>14了，则乙的目标状态变成10—（17-14）=7；加一次ans;

乙堆目标状态是7，只能由甲堆拿来，不过乙已经是8>7了，那么甲的目标状态变为10-(8-7)=9;加一次ans；
甲嗯哼。

procedure dg(tar,ned:longint);

begin
if tar=0 then exit
else
begin
if a[tar]=ned then dg(tar-1,ned1)
else
begin
if (a[tar]>ned) then begin inc(ans);dg(tar-1,ned1-(a[tar]-ned)); end
else if (a[tar]<ned) then
begin
inc(ans);
dg(tar-1,ned1+(ned-a[tar]));
end;
end;

end;
end;

从第一个判断到最后，不够就从后面拿，多了就加到后面。

#include<iostream>
using namespace std;
int main()
{
    int N, num[100], sum = 0, movetimes = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num[i];
        sum += num[i];
    }
    for (int i = 0; i < N-1; i++)
    {
        if (num[i] != sum / N) {
            movetimes++;
            num[i + 1] = num[i + 1] + num[i] - sum / N;
        }
    }
    cout << movetimes;
    return 0;
}

python
从左至右过一次即可

关键在于
**若i满足
前i-1项和 < i*k, 且 前i项和 >= i*k
则必有：
若i*k等于前n项和 需且仅需 i-1步 将前i项 复原
若i*k大于前n项和 需且仅需 i步 将前i项 复原
**
k：每叠平均数

n = int(input())
list_input = input().split()
list_a = []
for i in list_input:
    list_a.append(int(i))
sum_all = sum(list_a)
k = int(sum_all / n)

i = 0
j = 0
sum_i = 0
times = 0
while i < n:
    sum_i += list_a[i]
    while sum_i < (i - j + 1) * k:
        i += 1
        sum_i += list_a[i]
    if sum_i == (i - j + 1) * k:
        times += i - j
    else:
        times = times + (i - j) + 1
    sum_i = sum_i - (i - j + 1) * k
    i += 1
    j = i

print(times)

首先计算出每一堆与平均值的差，结果相对于0，多的给旁边，少的从旁边拿，要求移动后为0，O(n)的复杂度即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,ans=0;
    cin>>n;
    vector<int> a(n);
    for(i=0;i<n;i++)
        cin>>a[i];
    int ave=accumulate(a.begin(),a.end(),0)/n;
    for(i=0;i<n;i++)
        a[i]-=ave;
    for(i=1;i<n;i++)
        if(a[i-1]!=0)
            a[i]+=a[i-1],ans++;
    cout<<ans;
    return 0;
}

• Accepted
• # 状态 耗时 内存占用
• #1 Accepted 1ms 312.0 KiB
• #2 Accepted 1ms 324.0 KiB
• #3 Accepted 1ms 204.0 KiB
• #4 Accepted 1ms 200.0 KiB
• #5 Accepted 1ms 324.0 KiB

因为题目说一定有平均，所以将牌数化成与平均数的差值
然后直接从左到右移，就是最佳方案。

#include<iostream>
#include<algorithm>
using namespace std;
//呵呵
//大神万岁
//分割线--------------------------------------------------$
//结构定义区

//全局变量区
int pk[101],n,ans=0; 
//函数声明区

//主函数开始！
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>pk[i];
    }
    int all=0;
    for(int i=0;i<n;i++)
    {
        all+=pk[i];
    }
    int pj=all/n;
    for(int i=0;i<n;i++)
    {
        pk[i]-=pj;
    }
    for(int i=0;i<n;i++)
    {
        if(pk[i]==0) continue;
        else
        {
            pk[i+1]+=pk[i];
            pk[i]=0;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}
//函数实现区

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i,j=0,k=0;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i],k+=a[i];
for(i=0;i<n;i++)
if(a[i]!=k/n)
a[i+1]=a[i+1]+a[i]-k/n,j++;
cout<<j;
return 0;
}

先是没认真审题，忽略了纸牌只能移到相邻的堆上这件事……
之后又为了避免某一堆的牌数在移动过程中出现负数而写了一大堆代码，但实际上某一堆的牌数出现负数的是不影响后续计算的……
妈的阿库娅……
当个反面教材好了……

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int aver=0;
    int ans=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        aver+=a[i];
    }
    aver/=n;
    for(int i=0;i<n-1;i++)
    {
        if(a[i]>aver)
        {
            a[i+1]+=a[i]-aver;
            ans++;
        }
        else if(a[i]<aver)//简洁的正确示范
        {
            a[i+1]-=aver-a[i];
            ans++;
        }
        /*结果正确但走弯路的错误示范
        else if(a[i]<aver)
        {
            int ts=0;
            int be=i;
            ts+=a[i];
            while(a[i+1]+ts<(i-be+2)*aver)
            {
                ts+=a[i+1];
                i++;
            }
            a[i+1]-=(i-be+1)*aver-ts;
            ans+=i+1-be;
        }
        */
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
using namespace std;
int a[10001] = { 0 };
int main()
{
int n; //输入纸牌的堆数
cin >> n;
int ave = 0, step = 0; //算平均数
for (int i = 0; i < n; i++)
{
cin >> a[i];
ave += a[i];
}
ave /= n; //求得每一堆应当有的牌的数量
for (int i = 0; i < n; i++)
a[i] = a[i] - ave;

for (int i = 0; i < n - 1; i++)
{
if (a[i] != 0)
{
a[i + 1] += a[i];
a[i] = 0;
step++;
}
if (a[i] == 0)
continue;
}
cout << step;
return 0;
}

#include<cstdio>
main()
{
int n,a[1000],s=0,t=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s+=a[i];
}
s/=n;
for(int i=1;i<n;i++)
if(a[i]!=s)
{
t++;
a[i+1]-=s-a[i];
a[i]+=s-a[i];
}
printf("%d",t);
}
贪心

审题很重要。。刚开始一直没看到n的倍数、左右移的条件，写个半死。。

//花式秀宏w
#include <stdio.h>
#ifndef INDEX_I
int index_i=0;
#define INDEX_I
#endif
#define mapTo(data,n,function_body)\
    index_i=0;\
    for(;index_i<n;index_i++){\
        int x=data[index_i];\
        int * str_x=&data[index_i];\
        function_body;\
    }
#ifndef RANGE_I
int range_i=0;
#define RANGE_I
#endif
#define for_range(x)\
    range_i=0;\
    for(;range_i<x;range_i++)

int readInt(){
    int n=0;
    scanf("%d",&n);
    return n;
}
void fillInData(int * data,int n){
    for_range(n) data[range_i]=readInt();
}
int avg(int * data,int n){
    int sum=0;
    mapTo(data,n,sum+=x);
    return sum/n;
}
int main(){
    int n=readInt(),data[100];
    fillInData(data,n);
    int avg_value=avg(data,n);
    mapTo(data,n,*str_x-=avg_value);
    int step=0;
    mapTo(data,n,{
        if(x){
            data[index_i+1]+=x;
            step++;
        }
    });
    printf("%d",step);
    return 0;
}

#include<bits/stdc++.h>
int a[105];
int sum, count=0;
void work(int i,int j) {
    if(i==j) return;
    while(a[i]==0) i++;
    a[i+1]+=a[i];
    count++;
    a[i]=0;
    work(i+1, j);
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        sum+=a[i];
    }
    sum/=n;
    for(int i=1; i<=n; i++) a[i]-=sum;
    int i=1, j=n;
    while(a[i]==0) {
        i++;
        if(i==j+1) {
            printf("0");
            return 0;
        }
    }
    while(a[j]==0) j--;
    work(i,j);
    printf("%d", count);
    return 0;
}

想了我半天，结果这么简单....

#include<stdio.h>
int main(){
int a[10010],n,avg=0,s=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
avg+=a[i];
}
avg=avg/n;
for(int i=0;i<n;i++)
a[i]-=avg;
for(int i=1;i<n;i++){
if(a[i-1]) {
s++;
a[i]+=a[i-1];
}
}

printf("%d",s);
}

从左往右依次考虑。（负数可由后来的操作补上）
#include <iostream>
using namespace std;

int n;
int arr[105];

int main() {
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>arr[i];
sum+=arr[i];
}
sum=sum/n;
int step=0;
for(int i=1;i<n;i++){
if(arr[i]!=sum){
arr[i+1]=arr[i+1]+arr[i]-sum;
arr[i]=sum;
step++;
}
}
cout<<step;
return 0;
}