分糖果

题目描述

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

当糖果不能平均分配时, 小明可以选择从糖果盒中 (假设盒中糖果足够) 取出一个糖果或放回一个糖果.

小明最少需要多少次 (取出, 放回和平均分配均记一次), 能将手中糖果分至只剩一颗.

输入描述

抓取的糖果数 (< 10000000000)

输出描述

最少分至一颗糖果的次数

示例1

输入:

15

输出:

5

示例2

输入:

6

输出:

3

题解

动态规划的思路:

• 如果是奇数个糖果, 就有两种方法: 取一个再平分;放一个再平分. 我们可以分别计算它们的结果, 再求得其中的最小值
• 如果是偶数个糖果, 就先平均分一次
• 使用缓存存储中间结果, 加快运算

Python

import sys

def main():
    cache = {1: 0}

    # 缓存 + 递归
    def get_minimum_times(num: int) -> int:
        if num in cache:
            return cache[num]
        if num % 2 == 0:
            # 如果是偶数个
            # 平均分一次
            times = 1 + get_minimum_times(num // 2)
            cache[num] = times
            return times
        else:
            # 如果是奇数个, 有两种方式:
            # 取一个
            times1 = 1 + get_minimum_times(num + 1)
            # 放一个
            times2 = 1 + get_minimum_times(num - 1)

            # 求它们的最小值
            min_times = min(times1, times2)
            cache[num] = min_times
            return min_times

    sweet = int(input().strip())
    times = get_minimum_times(sweet)
    print(times)

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <unordered_map>

// 缓存 + 递归
int get_minimum_times(int num, std::unordered_map<int, int>& cache) {
  const auto iter = cache.find(num);
  if (iter != cache.end()) {
    return iter->second;
  }

  if (num % 2 == 0) {
    // 如果是偶数个
    // 平均分一次
    const int times = 1 + get_minimum_times(num / 2, cache);
    cache[num] = times;
    return times;
  } else {
    // 如果是奇数个, 有两种方式:
    // 取一个
    const int times1 = 1 + get_minimum_times(num + 1, cache);
    // 放一个
    const int times2 = 1 + get_minimum_times(num - 1, cache);
            
    // 求它们的最小值
    const int min_times = std::min(times1, times2);
    cache[num] = min_times;
    return min_times;
  }
}

int main() {
  std::unordered_map<int, int> cache;
  cache[1] = 0;

  int num_candies = 0;
  std::cin >> num_candies;

  const int times = get_minimum_times(num_candies, cache);
  std::cout << times << std::endl;

  return 0;
}

Rust

use std::collections::HashMap;
use std::io::{stdin, BufRead};

fn main() {
    // 缓存 + 递归
    fn get_minimum_times(num: usize, cache: &mut HashMap<usize, usize>) -> usize {
        if let Some(value) = cache.get(&num) {
            return *value;
        }
        if num % 2 == 0 {
            // 如果是偶数个
            // 平均分一次
            let times = 1 + get_minimum_times(num / 2, cache);
            cache.insert(num, times);
            times
        } else {
            // 如果是奇数个, 有两种方式:
            // 取一个
            let times1 = 1 + get_minimum_times(num + 1, cache);
            // 放一个
            let times2 = 1 + get_minimum_times(num - 1, cache);

            // 求它们的最小值
            let min_times = times1.min(times2);
            cache.insert(num, min_times);
            min_times
        }
    }

    let mut cache = HashMap::from([(1, 0)]);
    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let num_candies: usize = line.trim().parse().unwrap();

    let times = get_minimum_times(num_candies, &mut cache);
    println!("{times}");
}