自动搬运

查看原文

来自洛谷，原作者为

	2huk Where should my destinaion be at? 我问我自己。

搬运于2025-08-24 22:51:27，当前版本为作者最后更新于2023-10-22 15:00:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[CSP-J 2023] 小苹果

Description

有 $n$ 个苹果手机排成一排，标号 $1 \sim n$。接下来每天都会抢走一些苹果手机，每次从最左边的第 $1$ 个苹果手机开始，每隔 $2$ 个拿一个苹果手机。取完后将剩下的苹果手机重新排成一排。求：

1. 多少天能拿完所有苹果手机；
2. 第 $n$ 个苹果手机是在第几天拿的。

Solution

我们可以把「每隔 $2$ 个取一个苹果手机」这件事情这样理解：将苹果手机每 $3$ 个分一组，每次取这一组的第一个。

例如有 $11$ 个苹果手机：

标红的是这一轮拿的。如果最后剩下的不足以拼成 $3$ 个一组的，就拼成不完整的一组。

很显然，这一轮取走的苹果手机数量就是分成的组数，即 $\left \lceil \dfrac n3 \right \rceil$。那么我们暴力模拟这件事，每次 $n \gets n - \left \lceil \dfrac n3 \right \rceil$，看多少次操作后 $n$ 变成 $0$ 即可。这是第一问。

对于第二问，我们可以这样考虑。首先最后一个苹果手机一定是在最后一组的，那么如果想取走这个苹果手机，就相当于这个苹果手机在最后一组的第一个。例如有 $11$ 个和 $10$ 个苹果手机：

可以发现，只有在最后一组仅有 $1$ 个苹果手机时，最后一个苹果手机是这一组的第一个。也就等价于当 $n \bmod 3 = 1$ 时，可以在这一轮取到最后一个苹果手机。

那么我们在求第一问的暴力模拟时，判断当前的 $n$ 是否模 $3$ 为 $1$。若是，记录下来这是第几轮取苹果手机。这就是第二问的答案。

注意在第一次 $n \bmod 3 = 1$ 时就可以取到最后一个苹果手机了。往后如果还有这样的机会就不算了。

考虑计算时间复杂度。每次将 $n$ 减去 $\left \lceil \dfrac n3 \right \rceil$，也就大约是 $n \gets \dfrac 23n$。不妨将其大约看作 $n \gets \dfrac 12n$，也就是每次将 $n$ 缩小一半。因此这样计算的话时间复杂度为 $\Theta(\log_2 n)$。实际运行时会偏高。

Code

#include <iostream>
#include <cmath> 

using namespace std;

int n, res1, res2;

int main()
{
	freopen("apple.in", "r", stdin);
	freopen("apple.out", "w", stdout);
	
	cin >> n;
	
	for (int i = 1; ; ++ i )
	{
		if (n == 0) break;
		if (!res2 && n % 3 == 1) res2 = i;		// 只有在第一次 n % 3 == 1 时记录答案 
		n -= ceil(n / 3.0);
		++ res1;
	}
	
	cout << res1 << ' ' << res2 << '\n';
	
	return 0;	
}