把当前水果序列压成若干连续块，按轮删除每块最左元素，并在构建下一轮块序列时合并相邻同类块。
OJ: luogu
题目 ID: P7912
难度:普及/提高-
标签:模拟队列cspj
日期: 2026-06-18 15:15
题意
一排水果由
每一轮都要从当前每个块中取出最左边的那个水果，按从左到右顺序装成一个果篮。
重复这个过程直到所有水果都被取完，要求输出每一轮果篮里的水果编号。
思路
先看最直接的做法：每一轮都重新扫描整排还没取走的水果，重新分块，然后取出每个块最左边的水果。
这个暴力版最容易理解：
cpp
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> cur;
for (int i = 1; i <= n; i++) {
cur.push_back(i);
}
while (!cur.empty()) {
vector<int> take;
vector<int> nxt;
for (int i = 0; i < (int) cur.size(); ) {
int j = i;
while (j < (int) cur.size() && a[cur[j]] == a[cur[i]]) {
j++;
}
take.push_back(cur[i]);
for (int k = i + 1; k < j; k++) {
nxt.push_back(cur[k]);
}
i = j;
}
for (int i = 0; i < (int) take.size(); i++) {
if (i) cout << ' ';
cout << take[i];
}
cout << '\n';
cur.swap(nxt);
}
return 0;
}但这样每轮都要重扫全部剩余水果，代价太高。
关键观察是：
- 一个块在一轮里只会删掉最左边一个水果；
- 块内部剩余部分还是连续的；
- 真正会变化的是块与块之间的关系，尤其是相邻同类块可能在下一轮合并。
所以没必要每轮重建整排水果，只要维护“当前有哪些块”即可。
做法是：
- 先把原序列压成若干初始块；
- 用
cur_blocks表示当前轮的块顺序； - 依次处理每个块：
- 输出它当前块头的编号；
- 把块头向后移一格；
- 如果块还有剩余，就把它放进
next_blocks； - 如果
next_blocks最后一个块和它同类，就直接合并。
- 一轮结束后让
，进入下一轮。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
int n;
int a[maxn];
int nxt_pos[maxn];
int head_pos[maxn], tail_pos[maxn], block_val[maxn];
vector<int> cur_blocks, next_blocks;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int block_cnt = 0;
for (int i = 1; i <= n; ) {
int j = i;
while (j + 1 <= n && a[j + 1] == a[i]) {
j++;
}
block_cnt++;
head_pos[block_cnt] = i;
tail_pos[block_cnt] = j;
block_val[block_cnt] = a[i];
for (int p = i; p < j; p++) {
nxt_pos[p] = p + 1;
}
nxt_pos[j] = 0;
cur_blocks.push_back(block_cnt);
i = j + 1;
}
while (!cur_blocks.empty()) {
next_blocks.clear();
for (int id : cur_blocks) {
int x = head_pos[id];
cout << x << ' ';
head_pos[id] = nxt_pos[x];
if (head_pos[id] == 0) {
continue;
}
if (!next_blocks.empty() && block_val[next_blocks.back()] == block_val[id]) {
int last = next_blocks.back();
nxt_pos[tail_pos[last]] = head_pos[id];
tail_pos[last] = tail_pos[id];
} else {
next_blocks.push_back(id);
}
}
cout << '\n';
cur_blocks.swap(next_blocks);
}
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的核心不是复杂算法，而是换一个维护对象：
- 不去维护“当前整排水果”
- 而是维护“当前块的顺序”
这样每个水果只会被处理一次，整个过程就能线性完成。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
