均分纸牌（经典贪心）

1 题目描述

有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）。

2 输入输出格式

输入格式：

两行

第一行为：N（N堆纸牌，1≤N≤100）

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

输出格式：

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

输入输出样例 输入样例#1： 4 9 8 17 6

输出样例#1： 3

3 分析

这是一道经典的贪心算法入门题目，要想用最少的移动次数把所有牌堆都移到相等，正确的贪心策略显然是：每次都移动尽可能多的纸牌。

以正常人的思维来想，肯定是从纸牌数最多的牌堆开始往旁边的牌堆移动纸牌，但是如果要程序中模拟这个过程无疑是比较困难的。因为是计算机处理的缘故，我们可以移动负数张纸牌，且最后达到的效果一样。

一开始先求出牌数的平均值，然后从第1堆开始遍历到第n-1堆牌，如果堆中的牌数不等于平均值，就移动堆中的牌数与平均值的差值张牌（这里无论正负）。接着，下一堆接收到移动过来的牌后，如果牌数不等于平均值，就移动差值张牌…如此循环反复，计算移动次数即可。

4 代码

 1#include <iostream>
 2using namespace std;
 3const int maxn=10000+5;//数组大小比数据范围稍大
 4int a[maxn];
 5int main()
 6{
 7    int n;
 8    int ans=0,sum=0,t=0;//ans表示移动次数，t表示要移动的牌数
 9    cin>>n;
10    for(int i=0;i<n;i++)//输入数据
11    {
12        cin>>a[i];
13        sum+=a[i];
14    }
15    int avg=sum/n;//求平均值
16    for(int i=0;i<n-1;i++)//遍历每个牌堆（到最后一堆牌数一定等于平均值）
17    {
18        if(a[i]+t!=avg)//如果这个牌堆收到移动过来的牌后牌数不等于平均值，就需要移动
19        {
20            t=a[i]+t-avg;//计算移动的牌数，或正或负。
21            ans++;//移动移动次数加一
22        }
23        else
24        {
25            t=0;//不用移动就是移动0张且次数不变
26        }
27
28    }
29    cout<<ans<<endl;
30    return 0;
31}

以上就是用贪心思想求解均分纸牌问题的整个过程，感谢老铁：淡雅刺影的供稿，你们看懂了吗？