蓝桥杯2014年C组：分糖果

问题描述

有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：
每个小朋友都把自己的糖果分一半给左手边的孩子。
一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。
反复进行这个游戏，直到所有小朋友的糖果数都相同为止。
你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。

解题方案

代码

#include <iostream>

using namespace std;


bool check(int *arr, int n) {
    int temp = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i] != temp)
            return false;
    }

    return true;
}

int main() {

    int ans = 0;

    int n;
    int xiao[101];

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &(xiao[i]));
    }

    while (true) {

        if (check(xiao, n))
            break;

        int t = xiao[0];
        for (int i = 0; i < n - 1; i++) {
            xiao[i] = xiao[i] / 2 + xiao[i + 1] / 2;
            if (xiao[i] % 2) {
                xiao[i]++;
                ans++;
            }
        }
        xiao[n - 1] = xiao[n - 1] / 2 + t / 2;


        if (xiao[n - 1] % 2) {
            xiao[n - 1]++;
            ans++;
        }
    }

    printf("%d", ans);
    return 0;
}

输入

3
2 2 4

输出

4