P1031 均分纸牌——————贪心

淩亂°似流年 2022-03-31 11:40 175阅读 0赞

# [P1031 均分纸牌][P1031] #

## 题目描述 ##

有N堆纸牌，编号分别为 1,2,…,N。每堆上有若干张，但纸牌总数必为 N的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为 N−1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如N=4 4堆纸牌数分别为：

①9②8③17④6  
移动3次可达到目的：

从 ③ 取4张牌放到 ④ （9,8,13,10）-> 从 ③ 取33张牌放到 ②（9,11,10,10）-> 从 ② 取1张牌放到①（10,10,10,10）。

## 输入格式： ##

两行

第一行为：NN（NN 堆纸牌，1 \\le N \\le 1001≤N≤100）

第二行为： A 1 , A 2 , … , A n A\_1,A\_2, … ,A\_n A1,A2,…,An（N堆纸牌，每堆纸牌初始数， 1 ≤ A i ≤ 10000 1 \\le A\_i \\le 10000 1≤Ai≤10000 )

## 输出格式： ##

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

输入输出样例  
输入样例  
4  
9 8 17 6

输出样例  
3

--------------------

先找出来纸牌数量的平均值ave,  
然后对于每一对纸牌都让其减去这个平均值  
所以我们得到的结果就是，如果纸牌个数大于平均值，那么它就大于0，小于平均值，它就小于0

这样一来我们可以得出这样的策略：从左到右开始找，如果第i堆纸牌的个数 a i a\_i ai不等于0，那么移动次数就+1， a i + 1 &ThickSpace; + = &ThickSpace; a i a\_\{i+1\}\\; += \\;a\_i ai\+1\+=ai，一直处理到最后一个就行，应为题目保证纸牌总数必为N的倍数，所以不用担心数组越界

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

[P1031]: https://www.luogu.org/problemnew/show/P1080