免费建筑图纸下载网站国家反诈中心app下载

2025 A卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《分糖果》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

---

题目名称：分糖果

---

1. 知识点：贪心算法、数学分析
2. 时间限制：1秒
3. 空间限制：256MB
4. 限定语言：不限

---

题目描述

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

输入描述：
一个整数 n，表示初始抓取的糖果数（n < 10000000000）。

输出描述：
输出最少操作次数，使糖果数变为1。

示例：

• 输入：15
• 输出：5
• 说明：15+1=16; 16/2=8; 8/2=4; 4/2=2; 2/2=1。

---

Java

问题分析

题目要求将初始糖果数n通过最少次数的操作变为1。每次操作可以分半（偶数时），或调整糖果数（奇数时加1或减1），每次操作均计数。目标是找到最少操作次数。

---

解题思路

1. 偶数处理：直接分半，操作次数+1。
2. 奇数处理：分情况讨论：
   • 若n=3，减1更优。
   • 若n mod4 ==1，减1使后续步骤更少。
   • 若n mod4 ==3，加1使后续步骤更少。
3. 数学规律：利用二进制分析，消除连续1以减少操作步骤。

---

代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n = scanner.nextLong();System.out.println(minSteps(n));}private static int minSteps(long n) {int count = 0;while (n > 1) {if (n % 2 == 0) {       // 偶数直接分半n /= 2;count++;} else {                // 奇数分情况处理if (n == 3) {        // 特殊情况：3减1最优n--;} else if (n % 4 == 1) { // 模4余1时减1n--;} else {             // 模4余3时加1n++;}count++;             // 调整操作计数}}return count;}
}

---

代码详解

1. 输入处理：

   long n = scanner.nextLong();
   

   • 读取输入的整数n，使用long类型处理大数。

2. 主循环：

   while (n > 1) { ... }
   

   • 持续处理直到n变为1。

3. 偶数分支：

   if (n % 2 == 0) { n /= 2; count++; }
   

   • 偶数直接分半，操作次数+1。

4. 奇数分支：

   if (n == 3) { n--; }  
   else if (n % 4 == 1) { n--; }  
   else { n++; }
   

   • 根据数学规律选择加减操作，确保后续步骤最少。

5. 调整计数：

   count++;
   

   • 每次调整操作计数+1。

---

示例测试

1. 输入15：

   • 步骤：15→16→8→4→2→1，操作次数5。
   • 输出：1。

2. 输入3：

   • 步骤：3→2→1，操作次数2。
   • 输出：2。

3. 输入5：