刷题笔记合集🔗

分糖果

问题描述

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。

当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。

小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

输入格式

输入一个整数，表示抓取的糖果数（）。

输出格式

输出一个整数，表示最少分至一颗糖果的次数。

样例输入

15

样例输出

5

数据范围

• 糖果数量

题解

这个问题可以看作是：给定一个数字，每次可以将其折半（如果是偶数），或者加1/减1使其变成偶数再折半，最少需要多少步到达1。

思路分析：

1. 如果当前糖果数是1，已经达到目标，返回0
2. 如果当前糖果数是偶数，直接折半操作
3. 如果当前糖果数是奇数，有两种选择：
   • 加1变成偶数再折半
   • 减1变成偶数再折半

由于每次都要选择最少步数，这里采用递归分治的思路解决：

1. 递归计算当前状态到达目标需要的最少步数
2. 在奇数情况下分别尝试加1和减1，取较小的步数

值得注意的是，由于数据范围很大(< 10000000000)，直接使用暴力递归可能会超时。但由于每次折半操作，复杂度实际上是对数级的，这使得算法效率足够高。

对于较大的输入，可能存在多种路径到达1，但我们只需要找到最少步数的路径。通过递归回溯，能够找到这个最优解。

时间复杂度：O(log n)，因为每次操作至少将数字减半。 空间复杂度：O(log n)，递归栈的深度。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
num = int(input())

def min_steps(n, memo={}):
    """计算将n分到1的最少步数"""
    # 基础情况
    if n == 1:
        return 0
    
    # 检查是否已计算过
    if n in memo:
        return memo[n]
    
    # 如果是偶数，直接除以2
    if n % 2 == 0:
        memo[n] = 1 + min_steps(n // 2, memo)
    else:
        # 如果是奇数，比较加1和减1的情况
        add_one = 1 + min_steps(n + 1, memo)  # 加1操作
        sub_one = 1 + min_steps(n - 1, memo)  # 减1操作
        memo[n] =