P1031 均分纸牌

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1031

题目描述有 N 堆纸牌，编号分别为 1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1堆上取的纸牌，只能移到编号为 2的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N−1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4， 4堆纸牌数分别为：
① 9② 8 ③ 17 ④ 6
移动 3次可达到目的：
从 ③ 取 4张牌放到 ④ （ 9,8,13,10 ）
-> 从 ③ 取 3 张牌放到 ②（ 9,11,10,10）
-> 从 ② 取 1 张牌放到①（ 10,10,10,10 ）。
输入输出格式输入格式：


两行
第一行为：N （ N堆纸牌， 1≤N≤1001）
第二行为： A1,A2,…,An（ N 堆纸牌，每堆纸牌初始数， l≤Ai≤10000l  ）

输出格式：


一行：即所有堆均达到相等时的最少移动次数。

输入输出样例输入样例#1：49 8 17 6
输出样例#1： 3

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[500],sum,ans;
   
4. int i,j;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for(i=1;i<=n;i++)
   
9.     {
   
10.         cin>>a[i];
    
11.         sum+=a[i];
    
12.     }
    
13.     sum=sum/n;
    
14.     for(i=1;i<n;i++)
    
15.     {
    
16.             if(a[i]<sum){a[i+1]=a[i+1]-(sum-a[i]);a[i]=sum;ans++;}
    
17.             if(a[i]>sum){a[i+1]=a[i+1]+(a[i]-sum);a[i]=sum;ans++;}
    
18.     ///        for(j=1;j<=n;j++)cout<<a[j]<<" ";
    
19.     ///        cout<<endl;
    
20.     }
    
21.     ///cout<<sum<<endl;
    
22.     cout<<ans;
    
23.     return 0;
    
24. }

复制代码

吴语林

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <algorithm>
   
7. using namespace std;
   
8. int main(){
   
9.         int n,i,count=0,a[150]={0},all=0;
   
10.         scanf("%d",&n);
    
11.         for(i=1;i<=n;i++)
    
12.         {
    
13.                 scanf("%d",&a[i]);
    
14.                 all=all+a[i];
    
15.         }
    
16.         all=all/n;
    
17.         for(i=1;i<=n;i++)
    
18.         {
    
19.                 a[i]=a[i]-all;
    
20.         }
    
21.         for(i=1;i<n;i++)
    
22.         {
    
23.                 if(a[i]!=0)
    
24.                 {
    
25.                         a[i+1]=a[i+1]+a[i];
    
26.                         a[i]=0;
    
27.                         count++;
    
28.                 }
    
29.         }
    
30.         printf("%d",count);
    
31.     return 0;
    
32. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n,t,ava;
   
4. long long s;
   
5. int a[101];
   
6. int main()
   
7. {
   
8.     cin>>n;
   
9.     for(int i=0;i<n;i++){cin>>a[i];s+=a[i];}
   
10.     ava=s/n;
    
11.     for(int i=0;i<n;i++)a[i]-=ava;
    
12.     for(int i=0;i<n;i++)if(a[i]){a[i+1]+=a[i];t++;}
    
13.     cout<<t;
    
14.     return 0;
    
15. }
    

复制代码

universehyf

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
5. int n,a[110],c[110],p,ans;
   
6. int main()
   
7. {
   
8.     scanf("%d",&n);FOR(i,1,n) scanf("%d",&a[i]);
   
9.     FOR(i,1,n) c[i]=c[i-1]+a[i];
   
10.     p=c[n]/n;
    
11.     FOR(i,1,n-1) if(p*i!=c[i]) ans++;
    
12.     printf("%d",ans);
    
13.     return 0;
    
14. }

复制代码

universehyf

这道题完全不需要贪心。

引理：

1、纸牌一定可以分到一样多。（题目条件）

2、相邻两堆牌间最多只会移动纸牌一次。（最优方案）

每次移动可以看作相邻两堆中左边一堆i往右边一堆i+1移动x张

1)x>0 左往右移动1次

2)x<0 右往左移动1次

3)x=0 不移动。当且仅当此时牌堆1-i总牌数为i*总平均数张（牌堆1-i在之前的交换中纸牌总数保持不变）

代码很简单