题目描述：P1031 [NOIP2002 提高组] 均分纸牌

解题思路

  • 解题思路

    1、假设纸牌数可以为负数，那么对于每一堆纸牌，缺少的牌就向右侧的堆索要(即使使其变为负数)，多出的牌就送到右边的堆中，此时至多操作 $n-1$ 次将满足题意
    2、由于一次操作可以运送任意数量的牌，简单猜想证明可知：假设上面情况需要 $m$ 次操作，一定存在某种方案，通过调整操作顺序，使得这 $m$ 次操作合法(不出现负数)
    3、简单举例，共 $3$ 堆牌，每堆牌数量分别为 $\{ 1, 1, 7 \}$，易知平均为 $3$。对于第 $1$ 堆牌，向右索要 $2$ 张，此时变为 $\{ 3, -1, 7 \}$；对于第 $2$ 堆牌，向右索要 $4$ 张，变为 $\{ 3, 3, 3 \}$满足题意。同时通过调整操作顺序一定能使得操作合法，例如该例可先执行操作 $2$ 再执行操作 $1$，即使得操作合法，其他例子也可猜想得证
    4、所以不需要考虑负数的问题，按照上面的方法模拟即可

代码实现

  • 代码实现

    #include <bits/stdc++.h>
using namespace std;

const int N = 110;
int a[N];

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += a[i];
    int avg = sum / n;

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] < avg)
        {
            int k = avg - a[i];
            a[i] += k;
            a[i + 1] -= k;
            ans++;
        }
        else if (a[i] > avg)
        {
            int k = a[i] - avg;
            a[i] -= k;
            a[i + 1] += k;
            ans++;
        }
    }

    cout << ans;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

页底评论