利用每天剩余苹果数和最后一个苹果当前位置都按 floor(2x/3) 递推，直接在 O(log n) 内求出总天数与删除时刻。
OJ: luogu
题目 ID: P9748
难度:普及-
标签:模拟推导cspj
日期: 2026-06-18 21:39
题意
有 n 个苹果排成一列。每天会删除当前序列中位置为 1,4,7,... 的苹果，然后把剩余苹果重新按原顺序排成一列。
要求输出两件事：
- 全部苹果被删完需要多少天。
- 编号为
n的苹果在哪一天被删掉。
思路
先看一个可以直接验证过程的朴素模拟：
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> apples;
for (int i = 1; i <= n; ++i) {
apples.push_back(i);
}
int day = 0;
int removed_day = 0;
while (!apples.empty()) {
++day;
vector<int> next_apples;
for (int i = 0; i < (int)apples.size(); ++i) {
int pos = i + 1;
if (pos % 3 == 1) {
if (apples[i] == n) {
removed_day = day;
}
} else {
next_apples.push_back(apples[i]);
}
}
apples = next_apples;
}
cout << day << ' ' << removed_day << '\n';
return 0;
}朴素做法会真的维护还活着的苹果编号，但 n 最多到
关键观察是：如果当前还剩 m 个苹果，那么当天删掉的位置是 1,4,7,...，删掉的个数是
同理，若某个苹果当前位于第 p 个位置：
，说明它今天就会被删掉； - 否则它会保留下来，并在新队列中跑到第
个位置。
于是我们分别做两个递推：
- 用
不断压缩，统计删空需要多少轮。 - 用
pos追踪编号为n的那个苹果当前排在第几位，直到它第一次满足。
这样就把大规模删除过程压成了两个
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
long long rest = n;
long long total_days = 0;
while (rest > 0) {
++total_days;
// 每天拿走当前位置为 1,4,7,... 的苹果，剩下 floor(2*rest/3) 个。
rest = rest * 2 / 3;
}
long long pos = n;
long long removed_day = 0;
while (pos > 0) {
++removed_day;
if (pos % 3 == 1) {
break;
}
// 原来的第 pos 个苹果没被拿走，删除它左边若干苹果后位置变小。
pos = pos * 2 / 3;
}
cout << total_days << ' ' << removed_day << '\n';
return 0;
}复杂度
时间复杂度是
总结
这题表面上是反复删数组，真正有用的是“数量如何变化”和“目标元素的位置如何变化”。只抓住这两个递推，就能把过程直接算出来。