插队问题

题目描述

达达在买回家的火车票，因为正值春运，售票处排起了长队。

因为晚上室内光线很暗，所以很多人趁机插队。

现在给每个人赋予一个整数作为编号，告诉你每一个排队的人的编号，和他进入队列时的具体位置。

请你确定最终的队列顺序。

输入格式

输入可能包含多组测试用例。

对于每组测试用例：

• 第一行包含整数 $N$，表示排队的总人数
• 接下来 $N$ 行，每行两个整数 $P_i, V_i$，第 $i$ 行数据表示第 $i$ 个人进入队列时的位置以及他的个人编号

位置定义

一个人的 $P_i$ 值具体表示为当该人员进入队列时，他前面的人数。

例如：

• 如果一个人插到了队首，则其 $P_i$ 值为 $0$
• 如果插到了第三个位置（第二个人后面），则其 $P_i$ 值为 $2$

输出格式

每个测试用例，输出一行包含 $N$ 个整数（表示每个人的编号）的结果，表示最终的人员队列顺序。

每个结果占一行，同行数据之间空格隔开。

数据范围

• $1 \le N \le 200000$
• $0 \le V_i \le 32767$（编号范围）
• $0 \le P_i \le i-1$（第 $i$ 个人插入时，前面最多有 $i-1$ 个人）

输入样例

4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492

输出样例

77 33 69 51
31492 20523 3890 19243

样例解释

第一组测试用例：N=4

输入：

1. 0 77：第1个人插入到位置0（队首）
2. 1 51：第2个人插入到位置1（前面有1个人）
3. 1 33：第3个人插入到位置1（前面有1个人）
4. 2 69：第4个人插入到位置2（前面有2个人）

插入过程：

初始： 队列为空

第1步： 插入 (0, 77)

队列：[77]

第2步： 插入 (1, 51)
位置1表示前面有1个人，插入到第2个位置

队列：[77, 51]

第3步： 插入 (1, 33) 位置1表示前面有1个人，插入到第2个位置 原队列：[77, 51]

• 位置0：77
• 位置1：51（前面有1个人：77） 插入33到位置1（前面有1个人）：

队列：[77, 33, 51]

33插入到51前面

第4步： 插入 (2, 69) 位置2表示前面有2个人，插入到第3个位置 当前队列：[77, 33, 51]

• 位置0：77
• 位置1：33
• 位置2：51（前面有2个人：77和33） 插入69到位置2（前面有2个人）：

队列：[77, 33, 69, 51]

69插入到51前面

最终队列： 77 33 69 51

第二组测试用例：N=4

输入：

1. 0 20523：插入到队首
2. 1 19243：插入到位置1
3. 1 3890：插入到位置1
4. 0 31492：插入到位置0

插入过程：

初始： 队列为空

第1步： 插入 (0, 20523)

队列：[20523]

第2步： 插入 (1, 19243) 位置1表示前面有1个人

队列：[20523, 19243]

第3步： 插入 (1, 3890) 位置1表示前面有1个人，插入到第2个位置

队列：[20523, 3890, 19243]

第4步： 插入 (0, 31492) 位置0表示插入到队首

队列：[31492, 20523, 3890, 19243]

最终队列： 31492 20523 3890 19243

问题分析

关键点

• 第 $i$ 个人插入时，前面已经有 $i-1$ 个人
• $P_i$ 表示插入时前面的人数，所以插入位置是第 $(P_i+1)$ 个位置（从1开始计数）
• 后续插入的人会影响已有位置

暴力方法不可行

如果使用数组直接模拟插入操作：

• 每次插入需要移动后面所有元素
• 时间复杂度 $O(N^2)$，对于 $N=200000$ 不可行

逆向思维

从最后一个人开始考虑：

• 最后一个人插入时，队列已经确定（有 $N-1$ 个人）
• 倒数第二个人插入时，队列有 $N-2$ 个人，以此类推

但正向插入时，后面插入的人会影响前面人的位置。

树状数组/线段树优化

我们可以维护一个长度为 $N$ 的数组，初始每个位置为1（表示空位）。

对于第 $i$ 个人，他要插入到第 $P_i+1$ 个空位置。

使用树状数组/线段树可以：

1. 查询第 $k$ 个空位置在哪里
2. 将该位置标记为已占用（设为0）

算法步骤（从后往前处理）：

1. 初始化一个长度为 $N$ 的数组，所有位置为1（表示空位）
2. 从最后一个人（第 $N$ 个人）开始向前处理：
   • 他要插入到第 $(P_i+1)$ 个空位置
   • 使用树状数组/线段树查找第 $k$ 个空位置（$k = P_i+1$）
   • 将该位置分配给他
   • 将该位置标记为已占用（设为0）
3. 全部处理完后，按照位置顺序输出编号

为什么从后往前：

• 最后一个人的位置是确定的（不会受后面插入影响）
• 倒数第二个人的位置只受最后一个人影响，但我们已经知道最后一个人的位置
• 以此类推，从后往前可以确定每个人的最终位置

查找第k个空位置

使用树状数组维护前缀和，可以快速找到第 $k$ 个1（空位）的位置。

设 $sum(x)$ 表示前 $x$ 个位置中空位的数量（1的个数）。

我们需要找到最小的 $pos$ 使得 $sum(pos) = k$。

可以使用二分查找：

• 在 $[1, N]$ 范围内二分查找 $pos$
• 对于每个 $mid$，计算 $sum(mid)$
• 如果 $sum(mid) \ge k$，则可能在左边，否则在右边

树状数组查询前缀和是 $O(\log N)$，二分是 $O(\log N)$，总查找复杂度 $O(\log^2 N)$。

也可以使用倍增法在 $O(\log N)$ 内找到第 $k$ 个1的位置。

算法实现

树状数组实现

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 200010;

class BIT {
private:
    vector<int> tree;
    int n;
    
public:
    BIT(int size) : n(size), tree(size + 1, 0) {}
    
    void add(int idx, int val) {
        while (idx <= n) {
            tree[idx] += val;
            idx += idx & -idx;
        }
    }
    
    int sum(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
    
    // 查找第k个1的位置（k从1开始）
    int find_kth(int k) {
        int pos = 0, bitMask = 1;
        // 找到大于等于n的最小的2的幂
        while (bitMask <= n) bitMask <<= 1;
        bitMask >>= 1;
        
        while (bitMask) {
            int next = pos + bitMask;
            if (next <= n && tree[next] < k) {
                k -= tree[next];
                pos = next;
            }
            bitMask >>= 1;
        }
        return pos + 1; // 因为pos是前缀和<k的最大位置
    }
};

int main() {
    int N;
    while (cin >> N) {
        vector<pair<int, int>> people(N);
        for (int i = 0; i < N; i++) {
            cin >> people[i].first >> people[i].second;
        }
        
        BIT bit(N);
        // 初始化：所有位置都是空位（1）
        for (int i = 1; i <= N; i++) {
            bit.add(i, 1);
        }
        
        vector<int> result(N + 1, 0); // 1-based
        
        // 从后往前处理
        for (int i = N - 1; i >= 0; i--) {
            int pos = people[i].first; // 前面的人数
            int id = people[i].second; // 编号
            
            // 要插入到第 (pos+1) 个空位置
            int k = pos + 1;
            int actual_pos = bit.find_kth(k);
            
            result[actual_pos] = id;
            bit.add(actual_pos, -1); // 标记为已占用
        }
        
        // 输出结果
        for (int i = 1; i <= N; i++) {
            if (i > 1) cout << " ";
            cout << result[i];
        }
        cout << endl;
    }
    
    return 0;
}

线段树实现

也可以使用线段树，每个节点维护区间内空位的数量，支持：

1. 查询第 $k$ 个空位的位置
2. 更新某个位置的状态

时间复杂度

• 树状数组初始化：$O(N \log N)$
• 每次查找第 $k$ 个空位：$O(\log N)$（使用倍增法）
• 每次更新：$O(\log N)$
• 总复杂度：$O(N \log N)$，对于 $N=200000$ 可以接受

示例详细过程（第一组测试用例）

输入：

4
0 77  (P=0, V=77)
1 51  (P=1, V=51)  
1 33  (P=1, V=33)
2 69  (P=2, V=69)

从后往前处理：

初始： 树状数组所有位置为1（空位） 空位状态：[1, 1, 1, 1]

第4个人： (P=2, V=69)

• $k = P+1 = 2+1 = 3$（第3个空位）
• 查找第3个空位：位置3
• 分配：result[3] = 69
• 更新：位置3设为0 空位状态：[1, 1, 0, 1]

第3个人： (P=1, V=33)

• $k = P+1 = 1+1 = 2$（第2个空位）
• 查找第2个空位：位置2（因为位置1是第1个空位，位置2是第2个空位）
• 分配：result[2] = 33
• 更新：位置2设为0 空位状态：[1, 0, 0, 1]

第2个人： (P=1, V=51)

• $k = P+1 = 1+1 = 2$（第2个空位）
• 查找第2个空位：位置4（位置1是第1个空位，位置4是第2个空位）
• 分配：result[4] = 51
• 更新：位置4设为0 空位状态：[1, 0, 0, 0]

第1个人： (P=0, V=77)

• $k = P+1 = 0+1 = 1$（第1个空位）
• 查找第1个空位：位置1
• 分配：result[1] = 77
• 更新：位置1设为0 空位状态：[0, 0, 0, 0]

最终result：

• result[1] = 77
• result[2] = 33
• result[3] = 69
• result[4] = 51

输出：77 33 69 51

注意事项

1. 位置编号：树状数组通常使用1-based索引
2. 空位计数：$P_i$ 是前面的人数，所以要插入到第 $P_i+1$ 个空位
3. 从后往前处理：关键点，确保每个人的最终位置正确
4. 多组测试用例：题目说可能包含多组

时空限制

• 时间限制：1秒
• 空间限制：64MB

对于 $N=200000$，$O(N \log N)$ 算法可以接受。