【蓝桥杯】历届试题分糖果（模拟）

本文主要是介绍【蓝桥杯】历届试题分糖果（模拟），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

历届试题分糖果

问题描述

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

输入格式

程序首先读入一个整数 $N (2 < N < 100)$ ，表示小朋友的人数。
接着是一行用空格分开的 $N$ 个偶数（每个偶数不大于 1000，不小于 2 ）。

输出格式

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

样例输入

3
2 2 4

样例输出

4

—— 踏雪寻梅 ——

大多说人看到这道题的时候其实都感觉挺简单的（当然，确实不难），反正就是模拟这个分糖以及发糖的过程嘛，最后统计补发糖果的数量即可。但是，在模拟发糖过程时，便会出现一些问题。

我第一次模拟先是建立了一个 int 型数组 $c hi l d s$ 来存储每个小朋友所拥有的糖果数量，接着通过一个循环（初始值从最后一个开始），把当前的 $c hi l d s [i]$ 赋值为 $c hi l d s [i] /2$ 并加上 $c hi l d s [i - 1] /2$ ，即： $c hi l d s [i] = (c hi l d s [i] + c hi l d s [i - 1]) /2$ ，最后再为第一个小朋友单独写交换糖果的代码。

但事实是，无论 $i$ 初始从 1 开始还是从最后开始，总会出错！因为小朋友们在交换时，其实是一个环形结构，因此无论从那里作为切入口进去，都将错误地把当前切入的这个小朋友的糖果数默认为 $c hi l d s [i] /2$ 。而实际上，这个小朋友的糖果数量应该为 $c hi l d s [i] /2 + c hi l d s [i - 1] /2$ （或者为 $c hi l d s [i] /2 + c hi l d s [i + 1] /2$ ）。

并且仔细一点的同学应该发现了，在循环中，当你执行完了某次 $c hi l d s [i] = (c hi l d s [i] + c hi l d s [i - 1]) /2$ 后，对于下一次而言，其实这时的 $c hi l d [i]$ 已经不再是初始的那个 $c hi l d s [i]$ 了（当然， $c hi l d s [i - 1]$ 也类似）。因为当你的代码用到了这样的一个循环的时候，说明你已经默认这个分糖果的游戏是按序轮次一个一个进行的，而实际上，这个发糖的过程是所有小朋友同时开始分、发、接受的！（当然，理解错误有一部分是题目表意不明的原因）。

既然是同时发糖的，那么为何不多用两个数组来维护这个发糖的过程呢？因此，修正后的解题思路大致如下：

步骤一：用一个数组 $c hi l d s [i]$ 来存储初始情况下每个小朋友手上的糖果数，并建立两个数组 $c l d 1 [i]$ 和 $c l d 2 [i]$ 用以维护之后的游戏过程。
步骤二：模拟发糖过程（这是一重循环，结束条件即为所有小朋友的糖果都相同）：
- 通过一重循环将所有小朋友的糖果都除以 2 ，并将结果保存进入 $c l d 1 [i]$ 中；
- 通过一重循环把每个小朋友手上的糖果错位存储进 $c l d 2 [i]$ 中（注：首位小朋友需要单独错位，即 $c l d 2 [0] = c l d 1 [N - 1]$ ）；
- 更新每个小朋友手上的糖果数量，即 $c hi l d s [i] = c l d 1 [i] + c l d 2 [i]$ 。

—— 破云见雾 ——

下面给出基于以上思路的完整代码：

#include<iostream>
using namespace std;
int main()
{int N,i,childs[100],sum=0;int cld1[100],cld2[100];cin>>N;for(i=0;i<N;i++)cin>>childs[i];while(1){//二分处理for(i=0;i<N;i++)cld1[i]=childs[i]/2;for(i=1;i<N;i++)cld2[i]=cld1[i-1];cld2[0]=cld1[N-1];//合同处理for(i=0;i<N;i++)childs[i]=cld1[i]+cld2[i];int flag=childs[0];for(i=1;i<N;i++)if(childs[i]!=flag)break;//再次发糖if(i!=N){for(i=0;i<N;i++)if(childs[i]%2!=0)	//检测到需要发糖{childs[i]++;sum++;}}//退出else break;}cout<<sum<<endl;return 0;
}