均分纸牌 洛谷

均分纸牌 洛谷

---

---

解题思路

这道题用贪心算法，先计算出每个牌堆应有多少牌，然后从左往右遍历每一牌堆，如果当前牌堆多于应有牌数，则移动多余部分至下一牌堆，如果当前牌堆少于应有牌数，则将后边的牌堆遍历并累加，直到这些牌堆的牌数大于等于这些牌堆总的应有牌数，通过这种移动方式，最终便可以计算出最少的移动次数。

代码

#include 
using namespace std;
int a[10000];
int main()
{
    int n, sum = 0, need, time = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    need = sum / n;
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] > need)
        {
            a[i + 1] += (a[i] - need);
            time++;
            continue;
        }
        if (a[i] < need)
        {
            int temp = a[i];
            for (int j = 1;; j++)
            {
                temp += a[i + j];
                if (temp >= j * need)
                {
                    time += j;
                    a[i + j] = temp - j * need;
                    i += (j - 1);
                    break;
                }
            }
        }
    }
    cout << time << endl;
    return 0;
}