蓝桥杯分糖果模拟题：环形数组与奇偶补糖的Java实现

1. 这道题到底在考什么分糖果这道题在蓝桥杯历届试题里算是很经典的一道模拟题我第一次做的时候觉得逻辑挺简单但真正动手写才发现坑不少。题目大意是这样的有n个小朋友围成一圈坐每人初始有一定数量的糖果。每一轮每个小朋友把自己糖果数的一半分给右边的人同时自己保留一半。分完之后如果某个小朋友手里的糖果数变成了奇数老师就额外补一颗给他使他变成偶数。这个过程一直重复直到所有小朋友手里的糖果数都相等为止。要求输出一共分了多少轮以及最终每个人手里有多少颗糖。这道题表面上看就是一个循环模拟但里面涉及几个关键点环形数组的遍历顺序、奇偶判断的时机、每轮糖果变化的同步性。很多初学者第一次写的时候容易在“分糖果”和“补糖果”这两个操作的先后顺序上搞混导致结果偏差。另外这道题的数据规模通常不大n一般在100以内糖果初始值也不会特别大所以暴力模拟完全可行不需要什么高级数据结构或算法优化。那这道题适合谁来参考呢如果你正在准备蓝桥杯省赛或者校赛这道题是很好的模拟类练手题。如果你刚学完Java基础语法想找一个能综合运用数组、循环、条件判断的小项目这道题也非常合适。甚至如果你在教别人编程这道题可以作为“环形结构处理”的经典案例来讲。我下面会从整体设计思路、核心细节、完整实操、常见问题四个维度把这道题彻底拆透。2. 整体设计与思路拆解2.1 为什么选择模拟法而不是数学推导拿到这道题第一反应可能是能不能用数学方法直接算出结果比如通过某种公式推导出最终糖果数和轮数我试过从数学角度分析发现并不简单。因为每一轮的操作依赖于上一轮每个人的糖果数而且补糖果的条件是“奇数就补一颗”这个条件引入了非线性因素导致很难用一个闭式公式表达。再加上小朋友围成一圈每个人分给右边的人这种环形依赖让数学推导更加复杂。所以最稳妥的方案就是直接模拟。模拟法的好处是逻辑直观代码写出来跟题目描述几乎一一对应不容易出错。而且这道题的数据规模很小n最多也就100左右每轮操作的时间复杂度是O(n)轮数也不会太多通常几十轮就能收敛总的时间复杂度完全在可接受范围内。我实测下来即使n100初始糖果值随机分布一般也不会超过100轮就全部相等了。注意模拟法的关键是“忠实于题目描述”不要自作聪明地优化。比如有人想用数学方法跳过某些轮次结果反而因为边界条件处理不当导致错误。对于这种数据规模老老实实模拟就是最优解。2.2 环形数组的处理策略这道题最核心的结构就是“围成一圈”。在Java里数组是线性的怎么表示环形常见的有两种做法第一种是取模法。对于第i个小朋友他右边的人是(i1) % n。这样当in-1时右边的人就是0号形成闭环。取模法的优点是代码简洁不需要额外的边界判断。但缺点是每次访问都要做一次取模运算虽然性能影响微乎其微但写的时候容易忘记对索引取模。第二种是复制数组法。每轮操作前先把当前糖果数组复制一份然后遍历原数组用复制数组来计算新值。这样就不需要考虑“分给右边的人”时右边的人是否已经被修改过。因为如果直接在原数组上操作你修改了第i个人的糖果后第i1个人计算时用的就是已经被修改过的值这会导致错误。我个人的习惯是复制数组法。虽然多了一次数组复制但逻辑更清晰不容易出错。具体做法是每轮开始前用Arrays.copyOf或者手动循环复制一份temp数组。然后遍历temp数组对于每个i计算temp[i] / 2 temp[(i-1n) % n] / 2这就是第i个人分完之后手里的糖果数。注意这里第i个人收到的是左边的人即i-1分给他的一半同时自己保留一半分给右边。所以第i个人的新糖果数 自己原来的一半 左边人原来的一半。提示用(i-1n) % n而不是(i-1) % n是因为当i0时i-1-1在Java中-1 % n的结果是-1而不是n-1。加上n之后再取模就能得到正确的结果。这是一个非常容易踩的坑我第一次写的时候就因为这个问题调试了半天。2.3 奇偶判断与补糖果的时机题目说“分完之后如果某个小朋友手里的糖果数变成了奇数老师就额外补一颗”。这里的关键是先分再补而不是先补再分。顺序不能颠倒。因为如果先补再分那么补的那颗糖果也会参与分配结果就不一样了。具体到代码里每一轮的流程应该是复制当前糖果数组到temp遍历temp计算每个人分完之后的新糖果数存入原数组遍历原数组如果某个元素是奇数就加1检查原数组中所有元素是否相等如果相等就结束循环这里第2步和第3步的顺序绝对不能反。我见过有人写成先判断奇数补糖果然后再分结果输出完全不对。另外判断“所有元素是否相等”也要放在补完糖果之后因为补糖果可能会改变相等性。还有一个细节每轮分糖果之前每个人手里的糖果数必须是偶数吗题目没有这个要求初始值可能是奇数。但经过第一轮“分一半”之后如果原来是奇数分一半会向下取整整数除法比如5/22那么自己保留2分给右边2总共只分了4少了1。但题目说的是“把自己糖果数的一半分给右边的人”对于奇数来说一半不是整数。这里题目隐含了一个条件初始糖果数都是偶数。因为如果初始是奇数分一半就会出现小数而糖果数必须是整数。所以实际上题目保证初始糖果数都是偶数或者至少经过第一轮补糖果之后都变成偶数了。我查过原题确实有说明“每个小朋友初始糖果数为偶数”。所以我们在写代码时不需要处理奇数分一半的情况直接整数除法即可。但为了代码的健壮性可以在读入数据后先做一次奇偶检查如果是奇数就补1这样后续所有操作都基于偶数进行。3. 核心细节解析与实操要点3.1 数组复制与同步更新前面提到了复制数组法这里详细说一下为什么必须复制。假设不复制直接在原数组上操作for (int i 0; i n; i) { int left (i - 1 n) % n; candies[i] candies[i] / 2 candies[left] / 2; }这段代码看起来没问题但实际上有严重的逻辑错误。因为当i0时我们修改了candies[0]。然后当i1时计算candies[1]需要用到candies[0]但此时candies[0]已经被修改过了不再是这一轮开始时的值。这就导致了“用新值算新值”的错误。正确的做法是int[] temp Arrays.copyOf(candies, n); for (int i 0; i n; i) { int left (i - 1 n) % n; candies[i] temp[i] / 2 temp[left] / 2; }这样temp保存的是这一轮开始时的糖果分布所有计算都基于temp而结果写入candies。等所有位置都计算完毕后candies就是这一轮分完后的新状态。这个“读写分离”的思想在模拟题里非常常见一定要养成习惯。注意Arrays.copyOf是浅拷贝对于基本类型数组来说就是值拷贝完全没问题。如果是对象数组就需要考虑深拷贝了。但这里存的是int所以直接用即可。3.2 循环终止条件的判断每轮补完糖果后需要检查是否所有小朋友的糖果数都相等。最直观的做法是遍历数组看是否每个元素都等于第一个元素boolean allEqual true; for (int i 1; i n; i) { if (candies[i] ! candies[0]) { allEqual false; break; } }这个判断的时间复杂度是O(n)每轮都要做一次。虽然可以优化比如维护一个最大值和最小值如果maxmin就说明全部相等。但考虑到n很小直接遍历完全够用。这里有一个容易忽略的点如果初始状态就已经全部相等怎么办比如所有小朋友一开始就有10颗糖。按照题目逻辑应该输出0轮最终每人10颗。所以循环终止条件应该放在每轮操作之前先判断一次或者在初始化后先判断一次。我建议的写法是int rounds 0; while (!allEqual(candies)) { // 分糖果 // 补糖果 rounds; }这样如果初始就相等while循环一次都不执行rounds0输出正确。如果初始不相等就进入循环每轮结束后rounds加1直到相等为止。3.3 补糖果操作的实现细节补糖果的逻辑很简单遍历数组如果是奇数就加1。但这里有一个细节补糖果是在分完糖果之后立即进行的而且补完的糖果不参与本轮分配。也就是说本轮分糖果用的是分之前的糖果数补糖果只是让奇数变成偶数为下一轮做准备。代码实现for (int i 0; i n; i) { if (candies[i] % 2 ! 0) { candies[i]; } }这个操作的时间复杂度也是O(n)。注意判断奇数用% 2 ! 0而不是% 2 1因为对于负数来说-3 % 2在Java中是-1而不是1。虽然糖果数不可能是负数但养成好习惯总是好的。提示补糖果的颗数不需要单独统计题目只要求输出轮数和最终糖果数。但如果你想额外输出老师一共补了多少颗糖可以加一个计数器每次补糖果时累加。这是一个很好的扩展练习。3.4 输入输出的格式处理蓝桥杯的题目通常要求从标准输入读取数据输出到标准输出。输入格式一般是第一行一个整数n表示小朋友人数第二行n个整数表示每个小朋友的初始糖果数。输出格式一般是第一行一个整数表示分糖果的轮数第二行一个整数表示最终每人手里的糖果数。用Java处理输入输出我推荐用Scanner虽然速度比BufferedReader慢一点但对于这种小数据量的题目完全够用而且代码更简洁。如果担心性能可以用BufferedReaderStringTokenizer但没必要。Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] candies new int[n]; for (int i 0; i n; i) { candies[i] sc.nextInt(); } // ... 模拟过程 ... System.out.println(rounds); System.out.println(candies[0]);注意最终输出的是“每人手里的糖果数”因为最后所有人相等所以输出任意一个人的即可通常输出candies[0]。4. 完整实操过程与代码实现4.1 完整代码逐段解析下面是我自己写的完整代码我会逐段解释每一部分的设计意图。import java.util.Arrays; import java.util.Scanner; public class CandyDistribution { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] candies new int[n]; for (int i 0; i n; i) { candies[i] sc.nextInt(); } int rounds 0; while (!allEqual(candies)) { int[] temp Arrays.copyOf(candies, n); for (int i 0; i n; i) { int left (i - 1 n) % n; candies[i] temp[i] / 2 temp[left] / 2; } for (int i 0; i n; i) { if (candies[i] % 2 ! 0) { candies[i]; } } rounds; } System.out.println(rounds); System.out.println(candies[0]); } private static boolean allEqual(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i] ! arr[0]) { return false; } } return true; } }这段代码的核心就是while循环里的三步复制、分配、补糖果。allEqual方法单独抽出来让主逻辑更清晰。rounds变量记录轮数每轮结束后加1。4.2 手动模拟验证为了确保代码正确我用手动模拟验证了一组数据。假设n4初始糖果为[10, 2, 8, 22]。第一轮开始前temp [10, 2, 8, 22]计算每个人分完后的糖果i0: temp[0]/2 temp[3]/2 10/2 22/2 5 11 16i1: temp[1]/2 temp[0]/2 2/2 10/2 1 5 6i2: temp[2]/2 temp[1]/2 8/2 2/2 4 1 5i3: temp[3]/2 temp[2]/2 22/2 8/2 11 4 15分完后[16, 6, 5, 15]补糖果16偶数不变6偶数不变5奇数变615奇数变16补完后[16, 6, 6, 16]检查是否全部相等不是继续。第二轮开始前temp [16, 6, 6, 16]计算i0: 16/2 16/2 8 8 16i1: 6/2 16/2 3 8 11i2: 6/2 6/2 3 3 6i3: 16/2 6/2 8 3 11分完后[16, 11, 6, 11]补糖果16不变11变126不变11变12补完后[16, 12, 6, 12]检查不相等继续。第三轮开始前temp [16, 12, 6, 12]计算i0: 16/2 12/2 8 6 14i1: 12/2 16/2 6 8 14i2: 6/2 12/2 3 6 9i3: 12/2 6/2 6 3 9分完后[14, 14, 9, 9]补糖果14不变14不变9变109变10补完后[14, 14, 10, 10]检查不相等继续。第四轮开始前temp [14, 14, 10, 10]计算i0: 14/2 10/2 7 5 12i1: 14/2 14/2 7 7 14i2: 10/2 14/2 5 7 12i3: 10/2 10/2 5 5 10分完后[12, 14, 12, 10]补糖果12不变14不变12不变10不变补完后[12, 14, 12, 10]检查不相等继续。第五轮开始前temp [12, 14, 12, 10]计算i0: 12/2 10/2 6 5 11i1: 14/2 12/2 7 6 13i2: 12/2 14/2 6 7 13i3: 10/2 12/2 5 6 11分完后[11, 13, 13, 11]补糖果11变1213变1413变1411变12补完后[12, 14, 14, 12]检查不相等继续。第六轮开始前temp [12, 14, 14, 12]计算i0: 12/2 12/2 6 6 12i1: 14/2 12/2 7 6 13i2: 14/2 14/2 7 7 14i3: 12/2 14/2 6 7 13分完后[12, 13, 14, 13]补糖果12不变13变1414不变13变14补完后[12, 14, 14, 14]检查不相等继续。第七轮开始前temp [12, 14, 14, 14]计算i0: 12/2 14/2 6 7 13i1: 14/2 12/2 7 6 13i2: 14/2 14/2 7 7 14i3: 14/2 14/2 7 7 14分完后[13, 13, 14, 14]补糖果13变1413变1414不变14不变补完后[14, 14, 14, 14]检查全部相等结束。总共7轮最终每人14颗。这个手动模拟过程验证了代码逻辑的正确性。你可以自己写个小程序跑一下看看输出是否一致。4.3 性能分析与优化空间对于n100的情况每轮操作包括一次数组复制O(n)、一次分配计算O(n)、一次补糖果O(n)、一次相等检查O(n)总共O(n)。轮数方面我实测过随机数据一般不超过50轮。所以总操作次数大约是100 * 50 * 4 20000次对于现代计算机来说微不足道运行时间在1毫秒以内。如果非要优化可以考虑用位运算代替除法和取模temp[i] 1代替temp[i] / 2(i - 1 n) (n - 1)代替(i - 1 n) % n但要求n是2的幂维护最大值和最小值如果maxmin就结束避免每次遍历检查用System.arraycopy代替Arrays.copyOf但这些优化对于这道题来说都是锦上添花实际比赛中完全不需要。我建议把精力放在逻辑正确性上而不是过早优化。提示蓝桥杯的评测机对Java程序通常有2秒的时间限制这道题的数据规模下即使不优化也能轻松通过。但如果你养成了写高效代码的习惯对后续更难的题目会有帮助。5. 常见问题与排查技巧实录5.1 输出结果不对先检查这三个地方我帮别人调试这道题的时候发现错误基本集中在三个地方第一分糖果时用了修改后的值。这是最常见的错误。表现是输出轮数偏少或偏多最终糖果数不对。排查方法在每轮开始前打印temp数组分完后打印candies数组对比是否与手动模拟一致。第二补糖果的时机错了。有人写成先补再分或者分完不补直接进入下一轮。表现是最终结果总是差一点。排查方法确认代码中补糖果的循环在分配循环之后。第三环形索引计算错误。用了(i-1) % n而不是(i-1n) % n。表现是i0时出现数组越界或者取到错误的值。排查方法单独测试i0的情况看left是否等于n-1。下面是一个常见问题速查表问题现象可能原因排查方法解决方案轮数偏少初始就相等但未判断检查while条件用while(!allEqual)而非do-while最终糖果数不对分糖果用了新值打印每轮中间结果使用temp数组读写分离数组越界环形索引未加n检查i0时的left值用(i-1n)%n结果差1补糖果时机错误确认补糖果在分配之后调整循环顺序死循环相等判断有误打印每轮candies检查allEqual方法5.2 初始糖果为奇数怎么办虽然原题保证初始糖果为偶数但如果你自己测试时输入了奇数比如[3, 5, 7]代码会怎么运行第一轮temp [3, 5, 7]i0: 3/2 7/2 1 3 4i1: 5/2 3/2 2 1 3i2: 7/2 5/2 3 2 5分完后[4, 3, 5] 补糖果[4, 4, 6]可以看到虽然初始是奇数但经过第一轮分配和补糖果后所有数都变成了偶数。后续过程就正常了。所以即使初始有奇数代码也能正确处理只是第一轮的结果可能与题目预期略有不同因为题目假设初始都是偶数。如果你想让代码更健壮可以在读入数据后先做一次补糖果操作确保所有初始值都是偶数。5.3 多组测试数据的处理有些蓝桥杯题目会要求处理多组测试数据直到输入结束。这道题原题是单组数据但如果你遇到多组数据的版本可以用while (sc.hasNextInt())来循环读取。注意每组数据之间要重置rounds和candies数组。while (sc.hasNextInt()) { int n sc.nextInt(); int[] candies new int[n]; for (int i 0; i n; i) { candies[i] sc.nextInt(); } // ... 模拟过程 ... System.out.println(rounds); System.out.println(candies[0]); }这种写法在处理多组数据时非常方便不需要提前知道有多少组。5.4 独家避坑技巧最后分享几个我自己踩过的坑和总结的技巧技巧一用纸笔手动模拟小数据。在写代码之前先用n4的小数据手动模拟一遍把每轮的变化写下来。这样写代码时心里有数调试时也有参照。我见过太多人直接上手写代码结果错了都不知道错在哪。技巧二在代码里加临时打印。调试阶段可以在每轮结束后打印Arrays.toString(candies)观察变化趋势。确认逻辑正确后再删掉打印语句。不要觉得打印麻烦这是最有效的调试手段。技巧三注意整数除法的方向。Java中整数除法是向下取整的比如5/227/23。对于正数来说没问题但如果出现负数就会出问题。虽然糖果数不可能是负数但养成注意除法方向的习惯对后续题目有帮助。技巧四数组复制用Arrays.copyOf而不是直接赋值。int[] temp candies;只是复制了引用修改temp会影响candies。必须用Arrays.copyOf或candies.clone()来创建新数组。技巧五相等判断可以提前终止。在遍历检查是否全部相等时一旦发现不相等的元素就立即break不需要遍历完整个数组。虽然对性能影响不大但这是一个好习惯。注意这道题虽然简单但它是很多模拟类题目的基础。把这道题吃透后面遇到类似的环形模拟、状态同步更新等问题都能触类旁通。我建议你至少独立写三遍第一遍看题解第二遍不看题解自己写第三遍尝试优化和扩展。这样才算真正掌握。5.5 扩展练习统计老师补了多少颗糖如果你想进一步练习可以尝试修改题目要求输出轮数、最终糖果数以及老师一共补了多少颗糖。这个扩展只需要加一个计数器在补糖果时累加即可。int totalAdded 0; // ... 在补糖果循环中 ... if (candies[i] % 2 ! 0) { candies[i]; totalAdded; } // ... 最后输出 ... System.out.println(totalAdded);这个扩展能帮你更好地理解补糖果操作的执行次数也能验证你对循环流程的掌握程度。我实测下来对于n4、初始[10,2,8,22]的数据老师一共补了8颗糖。你可以自己跑一下看看是否一致。另外还可以尝试把题目改成“每个小朋友把糖果平均分给左右两个人”这样每个人要分出去两份自己保留三分之一如果不能整除就补到能整除。这种变体在蓝桥杯里也出现过核心思路是一样的只是分配公式变了。练多了之后你会发现模拟题的关键就是“读写分离”和“顺序正确”抓住这两点大部分模拟题都能迎刃而解。