P2541. 分糖果

解题思路

本题是一道比较有意思的题目。从题意描述到解题思路，个人都比较喜欢。

本题的数据量看似给得非常大（N < 10000000000），但是仔细思考可以发现，每一次我们都会近似地让糖果数量减半，因此糖果数减少到1的速度是对数级别的。

我们可以直接使用一个 O(logN) 的模拟算法来解决这个问题。

关键递推关系

考虑某一个特定的糖果数量 num，且到达 num 的操作次数为 time。当：

• num 是偶数的时候，我们获得数量 num // 2 的糖果，需要 time + 1 次操作。这里的 1 次操作，是减半操作。
• num 是奇数的时候，我们获得数量 (num+1) // 2 或 (num-1) // 2 的糖果，需要 time + 2 次操作。这里的 2 次操作，有 1 次是减半操作，有 1 次是 +1 或 -1 操作。

显然，对于任意的 num，如果已知对应的 time，我们就可以计算出其近似减半后的结果。而近似减半后的结果得到之后，我们又可以做类似的重复操作，直到最终糖果数量减少到 1。

递归实现

这种重复的过程，容易想到可以使用递归来完成。考虑递归三要素：

• 递归入口：传入初始值的当前数量 num = n，以及初始操作次数 time = 0
• 递归子问题：num 的减半过程，也就是上述的讨论。
• 递归终止条件：当 num 减少到 1 的时候，可以更新答案。

本题的递归过程和动态规划非常类似，可以多加以比较。