题目描述：
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
- 吃掉一个橘子。
- 如果剩余橘子数
n 能被 2 整除，那么你可以吃掉 n/2 个橘子。 - 如果剩余橘子数
n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。
每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
数据范围：
$1\le n \le 2\times 10^9$
题解：
操作一的次数有限，主要是需要靠操作二和操作三。
如果 $n$ 不能被 $2$ 和 $3$ 整除，就需要使用操作一，调整到能使用 $2$ 或 $3$ 。调整的次数为 $1$ 或 $2$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
unordered_map<int, int> mp;
int minDays(int n)
{
if (n <= 1)
return 1;
if (!mp.count(n))
mp[n] = 1 + min(n % 2 + minDays(n / 2), n % 3 + minDays(n / 3));
return mp[n];
}
};
|