题目描述
春运期间，火车站售票处排起了长队。有些人趁乱插队，现在需要根据每个人进入队列时的位置和编号，确定最终的队列顺序。
输入格式
输入可能包含多组测试用例。每组测试用例：
- 第一行包含整数 N，表示排队的总人数
- 接下来 N 行，每行两个整数 Pi, Vi
- Pi 表示第 i 个人进入队列时，他前面的人数（0表示队首）
- Vi 表示这个人的编号
输出格式
每个测试用例，输出一行包含 N 个整数的最终队列顺序。
问题分析
核心难点
如果正着处理，每次插入操作都会影响后面所有人的位置，导致时间复杂度为 O(n²)，无法满足 N ≤ 200000 的数据规模。
关键转化：逆序处理
从最后一个人开始往前处理：
- 最后一个人的位置是确定的（因为后面没有人会影响他）
- 对于第 i 个人，他应该插入到当前空位中的第 p[i]+1 个位置
- 使用树状数组维护空位信息，二分查找确定插入位置
算法详解
树状数组（Fenwick Tree）
树状数组是一种高效的数据结构，用于维护数组前缀和的动态查询和更新。其核心优势在于：
- 单点更新 O(log n)：修改一个元素的值
- 区间查询 O(log n)：查询前缀和
在本题中，树状数组用于维护每个位置是否为空位：
- tr[i] 表示前 i 个位置共有多少个空位
- 初始时所有位置都是空位（值为1）
- 当一个人占据位置后，该位置的值变为0
二分查找第 k 个空位
通过树状数组的 sum(mid) 函数，可以快速得到前 mid 个位置有多少空位。
二分查找的核心思想：找到最小的位置 x，使得 sum(x) ≥ k，这个 x 就是第 k 个空位的位置。
这体现了「可二分性」：随着位置右移，空位数量单调递增。
处理过程示例
以输入样例为例：
输入：
4
0 77 // 第1个人插到位置0（队首）
1 51 // 第2个人插到位置1（第1个人后面）
1 33 // 第3个人插到位置1
2 69 // 第4个人插到位置2处理过程：
初始化：[1,1,1,1] // 1表示空位
处理第4人：p[4]=2，找第3个空位 → 位置3 → [1,1,0,1]
处理第3人：p[3]=1，找第2个空位 → 位置2 → [1,0,0,1]
处理第2人：p[2]=1，找第2个空位 → 位置4 → [1,0,0,0]
处理第1人：p[1]=0，找第1个空位 → 位置1 → [0,0,0,0]
最终结果：[77,33,69,51]复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 初始化树状数组 | O(n log n) | O(n) |
| 每人找位置 | O(log² n) | |
| 总复杂度 | O(n log² n) |
对于 N = 200000，O(n log² n) 完全可以接受。
完整代码实现
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int n; // 排队的总人数
int p[N], v[N]; // p[i]: 位置, v[i]: 编号
int ans[N]; // 最终队列顺序
int tr[N]; // 树状数组
// lowbit 函数：返回 x 二进制的最低位 1
int lowbit(int x) {
return x & -x;
}
// 树状数组单点更新
void add(int x, int c) {
for (; x <= n; x += lowbit(x))
tr[x] += c;
}
// 树状数组前缀和查询
int sum(int x) {
int res = 0;
for (; x; x -= lowbit(x))
res += tr[x];
return res;
}
// 二分查找第 k 个空位的位置
int find(int k) {
int l = 1, r = n, pos;
while (l <= r) {
int mid = (l + r) >> 1;
if (sum(mid) >= k) {
pos = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return pos;
}
int main() {
while (~scanf("%d", &n)) { // 读取多组数据
// 读入数据
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i], &v[i]);
// 初始化树状数组：所有位置都是空位
for (int i = 1; i <= n; i++)
add(i, 1);
// 逆序处理：最后一个人先确定位置
for (int i = n; i >= 1; i--) {
int k = p[i] + 1; // 找第 k 个空位
int pos = find(k); // 二分查找位置
ans[pos] = v[i]; // 放置编号
add(pos, -1); // 占用该位置
}
// 输出结果
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
printf("\n");
}
return 0;
}关键要点总结
- 逆序处理：避免正序处理时位置动态变化的问题
- 树状数组：高效维护空位信息，支持 O(log n) 的更新和查询
- 二分查找：利用单调性快速定位第 k 个空位
- 索引转换：题目中 p 从 0 开始计数，实际找第 p+1 个空位
同类题目拓展
本题的核心思想（逆序 + 树状数组 + 二分）可以应用于以下场景：
- 动态插队问题
- 序列中第 k 大的元素查找
- 离线处理排序问题
掌握这一思路对于解决算法竞赛中的动态序列问题非常有帮助。