当前位置：首页 > news >正文

CSP-J（入门级）2023年T1小苹果：从模拟到数学优化的解题思路

news 2026/5/12 16:46:45

1. 题目解析与模拟解法

我们先来看题目描述：桌上有n个苹果排成一列，每天从第1个苹果开始，每隔2个苹果拿走1个（即拿走第1、4、7...个苹果），然后将剩下的苹果重新排列。需要计算拿完所有苹果的天数，以及编号为n的苹果是在第几天被拿走的。

这个题目看起来简单，但数据范围n≤1e9意味着直接模拟会超时。不过作为基础，我们先实现一个模拟解法来理解题目规律。

1.1 基础模拟实现

用数组标记苹果状态是最直观的解法。我写了一个版本后发现当n=1e6时，在普通电脑上运行就需要几秒钟，显然无法通过1e9的数据：

#include <bits/stdc++.h> using namespace std; bool a[1000005]; // 标记苹果是否存在 int main() { int n, days = 0, last_day = 0; cin >> n; for(int i=1; i<=n; i++) a[i] = true; int remaining = n; while(remaining > 0) { days++; int count = 0; // 当天拿走的苹果数 for(int i=1; i<=n; i++) { if(a[i]) { count++; if(count % 3 == 1) { // 拿走第1/4/7...个 a[i] = false; remaining--; if(i == n) last_day = days; } } } } cout << days << " " << last_day; return 0; }

这个解法的时间复杂度是O(days*n)，当n=1e9时days约30次（每次减少约1/3），但3e9次操作仍然超时。不过它帮助我们理解了两个关键点：

每轮拿走的苹果数量大约是当前总数的1/3
最后一个苹果被拿走的时机需要特殊判断

1.2 优化空间复杂度

原始解法用bool数组会消耗O(n)空间，当n=1e9时内存直接爆掉。改用vector可以动态分配内存：

vector<bool> a(n+1, true); // 动态分配

实测n=1e7时内存约1.2MB，但n=1e9仍然不可行。这说明必须寻找数学规律而非模拟。

2. 数学规律分析

观察苹果被拿走的顺序，可以发现每轮操作后剩下的苹果数量呈规律性变化。让我们用n=8的样例来演示：

初始：1 2 3 4 5 6 7 8
第1天：拿走1,4,7 → 剩下2 3 5 6 8
第2天：拿走2,6 → 剩下3 5 8
第3天：拿走3 → 剩下5 8
第4天：拿走5 → 剩下8
第5天：拿走8

关键发现：

每轮剩下的苹果数约为上一轮的2/3
当n%3==1时，最后一个苹果会在当前轮被拿走

2.1 计算总天数

每轮苹果数量变化遵循：n → n - ceil(n/3)
这等价于n → floor(2n/3)。用数学归纳法可以证明：

当n=1时，1轮拿完
假设f(k)表示k个苹果需要的轮数
则f(n) = f(n - ceil(n/3)) + 1

这个递推式可以转化为循环实现：

int days = 0; while(n > 0) { days++; n -= (n + 2) / 3; // ceil(n/3)的等价写法 }

2.2 判断最后一个苹果

编号为n的苹果被拿走的时机：当剩余苹果数满足n%3==1时。因为此时n位于要拿走的序列中（第1,4,7...个）。

需要注意：一旦被标记后就不需要再判断，因为苹果只能被拿走一次。实现时可以用一个flag来记录：

int last_day = 0; while(n > 0) { days++; if(n % 3 == 1 && last_day == 0) { last_day = days; } n -= (n + 2) / 3; }

3. 最终数学解法

结合上述分析，我们得到O(logn)的解法：

#include <iostream> using namespace std; int main() { int n, days = 0, last_day = 0; cin >> n; while(n > 0) { days++; if(last_day == 0 && n % 3 == 1) { last_day = days; } n -= (n + 2) / 3; // 等价于ceil(n/3) } cout << days << " " << last_day; return 0; }

这个算法为什么高效？因为n每次至少减少1/3：