题目 1431: 蓝桥杯第五届真题-分糖果

题目描述:

有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：

每个小朋友都把自己的糖果分一半给左手边的孩子。

一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。

反复进行这个游戏，直到所有小朋友的糖果数都相同为止。

你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。

代码:

package lanqiao;
 
import java.math.BigInteger;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ar1 = new int[n]; //原本糖果的数目
        int[] ar2 = new int[n]; //给左孩子的糖果数目
        for(int i = 0;i < n;i ++)
        {
            ar1[i] = sc.nextInt();
        }
        boolean flag = true;
        int sum = 0;
        while(flag)
        {
            flag = false;
            for(int i = 0;i < n;i ++)
            {
                if(i == n - 1){
                    ar2[0] = ar1[i] / 2;
                    ar1[i] = ar1[i] / 2;
                }else{
                    ar2[i + 1] = ar1[i] / 2;
                    ar1[i] = ar1[i] / 2;
                }
            }
            for(int i = 0;i < n;i ++)
            {
                ar1[i] += ar2[i]; //加上旁边给的糖果
            }
            for(int i = 0;i < n;i ++)
            {
                if(ar1[i] % 2 != 0){
                    ar1[i] += 1;
                    sum ++;
                }
                if(ar1[0] != ar1[i]){ //判断孩子们手中糖果是否相等
                    flag = true;
                }
            }
        }
        System.out.println(sum);
    }
}