各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

第五届蓝桥杯Java B——分糖果

March 9, 2019 • Read: 421 • 算法

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

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

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

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

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

【格式要求】

程序首先读入一个整数N(2<N<100),表示小朋友的人数。

接着是一行用空格分开的N个偶数(每个偶数不大于1000,不小于2)

要求程序输出一个整数,表示老师需要补发的糖果数。

例如:输入
3
2 2 4
程序应该输出:
4

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] arr = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++)
            arr[i] = cin.nextInt();
        
        while (true) {
            int tmp = arr[0];
            for (int i = 0; i < n - 1; i++) {
                arr[i] += arr[i + 1] >> 1;
                arr[i + 1] /= 2;
            }
            arr[n - 1] += tmp >> 1;
            arr[0] -= tmp >> 1;
            if (check(arr))
                break;
            for (int i = 0; i < n; i++)
                if (arr[i] % 2 != 0) {
                    ans += 1;
                    arr[i]++;
                }
        }
        System.out.println(ans);
    }

    static boolean check(int[] arr) {
        int t = arr[0];
        for (int i = 1; i < arr.length; i++)
            if (arr[i] != t)
                return false;
        return true;
    }
}
Archives Tip
QR Code for this page
Tipping QR Code