ZYF039 吃到N个橘子的最少天数
ZYF039 吃到N个橘子的最少天数
【算法标签】 动态规划、记忆化搜索、BFS
【语法标签】 :unordered_map、min、队列(queue)、记忆化搜索
厨房里有 个橘子,你每天必须选择以下三种方案之一来吃橘子:
- 吃掉 1 个橘子。
- 如果当前剩余橘子数 能被 整除,可以吃掉 个橘子(剩下一半)。
- 如果当前剩余橘子数 能被 整除,可以吃掉 个橘子(吃掉三分之二,剩下三分之一)。
求:吃掉所有橘子所需的最少天数。
数据范围: 最大可达 (二十亿)。
二、解题思路
2.1 为什么不能用简单贪心
拿到这道题,很多同学第一反应是:"能吃多就吃多"——优先用操作 3(吃 ),不行再操作 2(吃一半),最后才操作 1(吃 1 个)。
这个想法很自然,但它是错误的。来看一个反例:
n = 10:
- 简单贪心:10 不能被 3 整除,也不能被 2 整除(等等,10 % 2 == 0)→ 吃 5 个剩 5 → 5 不能被 2 或 3 整除 → 吃 1 个剩 4 → 4 % 2 == 0 吃 2 个剩 2 → 吃 1 个剩 1 → 吃 1 个。共 5 天。
- 最优解:10 - 1 = 9(吃 1 个)→ 9 % 3 == 0,吃 6 个剩 3 → 3 % 3 == 0,吃 2 个剩 1 → 吃 1 个。共 4 天。
可以看出,有时候先减 1 让数字变得能被 3 整除,比直接除 2 更划算。
再比如 n = 11:
- 贪心:11 不能除 2 或 3 → 减 1 到 10 → 10 % 2 == 0 吃 5 剩 5 → ... 共 6 天。
- 最优:11 - 2 = 9(连续吃两天 1 个)→ 9 % 3 == 0 吃 6 剩 3 → 吃 2 剩 1 → 吃 1。共 5 天。
结论:每一个状态都有三种选择,必须全面搜索才能得到最优解。
2.2 从搜索到记忆化
最朴素的想法是用 BFS 或 DFS 搜索所有可能:
从 n 出发,每一步尝试三种操作,直到变为 0。
记录最短步数。但 最大 ,裸搜索会超时。
观察:在搜索过程中,同一个数字可能被多次访问。比如从 出发,走"减 1 再除 3"会到 ,走"除 2 再减 1 再除 3"也可能到 。我们只需要计算一次 的最优解,以后直接用。
这就是记忆化搜索(Memoization):用一个 unordered_map<int, int> 记录每个 对应的答案,遇到已计算过的直接返回。
2.3 状态转移方程
设 表示吃光 个橘子的最少天数:
- 操作 1 吃 1 个:
- 操作 2 吃一半:(前提 是偶数)
- 操作 3 吃 :(前提 是 3 的倍数,吃掉 ,剩下 即 )
2.4 进一步优化(关键)
如果 很大(比如 ),递归 会非常深(可能要递归 10 亿层),程序会爆栈或超时。
聪明的做法:不直接递归 ,而是思考"减 1"的目的是什么?
减 1 的唯一目的,是让 变成能被 2 或 3 整除的数,然后执行除法。每次除法会让 大幅缩小,这才是高效的。
因此,对于当前的 ,我们只有两个"有意义"的方向:
- 方向 A:一直减 1 直到能被 2 整除(需要减 步),然后除 2。
- 方向 B:一直减 1 直到能被 3 整除(需要减 步),然后除 3。
优化后的递推式:
其中 就是"减到能被 2 整除所需的减 1 步数",同理 。
边界:,。
注意:当 时,,,所以 ?不对,这里要小心。让我重新审视。
实际上 时:
- 方向 A:,,代价 ,加上当前一步 = 2。即:1 天除 2(吃 1 个剩 1),1 天吃 1 个 = 共 2 天。
- 方向 B:,,代价 ,加上当前一步 = 3。即:2 天各吃 1 个到 0。但这里方向 B 中"当前一步"是除 3,而 ,根本不能除 3...
实际上这个公式有个隐含假设:我们先做 次减 1 操作,然后做一次除 2 操作。这一共是 步,然后处理剩下的 。所以递推式应该写为:
边界:,。
验证 :。正确:吃 1 个剩 1(不,2%2==0,可以吃 1 个剩 1),再吃 1 个,共 2 天。
验证 :
- 所以
- 所以 。与样例一致!
2.5 手动模拟样例 1
n = 10,用记忆化搜索:
f(10) = min( f(5)+0+1 , f(3)+1+1 ) // 除2:剩5, 除3需先减1步
= min( f(5)+1 , f(3)+2 )
计算 f(5):
f(5) = min( f(2)+1+1 , f(1)+2+1 ) // 除2需先减1步, 除3需先减2步
= min( f(2)+2 , f(1)+3 )
计算 f(2):
f(2) = min( f(1)+0+1 , f(0)+2+1 ) = min(2, 3) = 2
→ f(5) = min(2+2, 1+3) = 4
计算 f(3):
f(3) = min( f(1)+1+1 , f(1)+0+1 ) = min(1+2, 1+1) = 2
// 除3: n%3==0, n%3=0, 所以+0+1
// 除2: n%2=1, 需要减1步到2再除2, 所以+1+1
→ f(10) = min(4+1, 2+2) = 4答案是 4 天。具体操作:10→9(减1)→3(吃6)→1(吃2)→0(吃1)。共 4 天。
三、参考代码
基础版(记忆化搜索,直观但大数会爆栈)
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> memo;
int dfs(int n) {
if (n <= 1) return n; // 0个橘子0天,1个橘子1天
if (memo.count(n)) return memo[n];
int ans = dfs(n - 1) + 1; // 方案1:吃1个
if (n % 2 == 0) // 方案2:吃一半
ans = min(ans, dfs(n / 2) + 1);
if (n % 3 == 0) // 方案3:吃2/3,剩1/3
ans = min(ans, dfs(n / 3) + 1);
return memo[n] = ans;
}
int main() {
int n;
cin >> n;
cout << dfs(n) << endl;
return 0;
}上面代码对于 会因递归 而超时或爆栈,不建议直接使用。
优化版(推荐,可处理 )
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> memo;
int dfs(int n) {
if (n <= 1) return n; // 边界
if (memo.count(n)) return memo[n];
// 关键优化:不直接调用 dfs(n-1)
// 而是计算减到能被2或3整除需要几步,然后做除法
int ans = min(
dfs(n / 2) + (n % 2) + 1, // 减 n%2 步 + 1次除2
dfs(n / 3) + (n % 3) + 1 // 减 n%3 步 + 1次除3
);
return memo[n] = ans;
}
int main() {
int n;
cin >> n;
cout << dfs(n) << endl;
return 0;
}解释:
n % 2就是当前数字离最近的能被 2 整除的数差多少步"减 1"。比如 n=11,n%2=1,先花 1 天吃 1 个变成 10,再花 1 天吃一半变成 5。总共就是dfs(5) + 1 + 1 = dfs(n/2) + n%2 + 1。
BFS 版本(另一种思路,适合理解状态空间)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<int, int> dist; // dist[x] = 从n到x的最少天数
queue<int> q;
dist[n] = 0;
q.push(n);
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == 0) {
cout << dist[cur] << endl;
return 0;
}
int d = dist[cur];
// 操作1:吃1个
if (!dist.count(cur - 1)) {
dist[cur - 1] = d + 1;
q.push(cur - 1);
}
// 操作2:吃一半
if (cur % 2 == 0 && !dist.count(cur / 2)) {
dist[cur / 2] = d + 1;
q.push(cur / 2);
}
// 操作3:吃2/3
if (cur % 3 == 0 && !dist.count(cur / 3)) {
dist[cur / 3] = d + 1;
q.push(cur / 3);
}
}
return 0;
}BFS 版同样要注意 很大时减 1 路径会很长。实际可用优化版 BFS(只入队能被 2 或 3 整除的状态)。
四、复杂度分析
- 时间复杂度:。每次递归 至少减半(除 2 或除 3),递归深度约为 ( 时)。虽然记忆化会访问不同的 、 等分支,但状态数仍然很少(实际不超过几百个)。
- 空间复杂度:。记忆化表存储的状态数和递归栈深度均为 。
【易错点】
操作 3 的理解:吃掉 个,剩下 个。所以新状态是 ,不是 (虽然结果一样)。代码中直接写
dfs(n / 3)。不能直接递归 : 很大时
dfs(n-1)会导致递归层数爆炸。必须用n%2和n%3来跳过连续的减 1 操作。边界条件:(没有橘子不需要吃),。注意 、 等小值的正确性。
unordered_mapvsmap:本题unordered_map更快( 平均),但如果编译器不支持 C++11 可以用map(,状态数少影响不大)。
