本文共 2464 字，大约阅读时间需要 8 分钟。
队列排序问题是一道经典的算法题，涉及到数据结构的高效应用。我们需要根据每个人加入时的前面人数p[i]和权值v[i]，确定最终队列中的权值序列。以下是解决这个问题的详细思路和代码实现。
问题分析：每个人加入队列时会给出前面有多少人，这意味着他们的位置取决于队列中已有的成员。为了确定最终队列，我们需要逆序处理每个人的位置信息。
线段树应用：线段树是一种高效的数据结构，适用于范围查询和更新操作。我们使用线段树来维护队列中的可用位置，逆序处理每个人时，查询可用位置并更新线段树。
逆序处理：从最后一个到第一个处理每个人，确保每次查询的位置是正确的。查询得到的位置即为他们在最终队列中的位置，然后将该位置从线段树中去除，继续处理下一个。
#include#include using namespace std;struct Node { int l, r, len;};void build(Node* tree, int l, int r) { tree->l = l; tree->r = r; tree->len = r - l + 1; if (l == r) return; int mid = (l + r) / 2; build(tree + 1, l, mid); build(tree + 2, mid + 1, r);}int query(Node* tree, int k) { if (tree->len == 0) return -1; if (k == 1) return tree->l; if (k > tree->len) return -1; int mid = (tree->l + tree->r) / 2; if (k <= tree->len / 2) { return query(tree + 1, k); } else { return query(tree + 2, k - tree->len / 2); }}int main() { int n; while (scanf("%d", &n) != EOF) { Node* tree = new Node; build(tree, 1, n); int p[n], v[n]; for (int i = 1; i <= n; ++i) { p[i] = readInt(); v[i] = readInt(); } int ans[n]; for (int i = n; i >= 1; --i) { int pos = query(tree, p[i] + 1); if (pos == -1) continue; ans[pos] = v[i]; // Update the tree by removing the pos tree->len--; int l = tree->l, r = tree->r; if (l == r) { tree = new Node; build(tree, l, r); } else { int mid = (l + r) / 2; if (pos <= mid - l + 1) { build(tree + 1, l, mid); } else { build(tree + 2, mid + 1, r); } tree = tree + (pos <= mid - l + 1 ? 1 : 2); } } for (int i = 1; i <= n; ++i) { if (ans[i] != 0) { printf("%d ", ans[i]); } } printf("\n"); } return 0;}int readInt() { int x = 0, f = 0; while (!isdigit(ReadChar())) { f ^= ReadChar() == '-'; ReadChar(); } while (isdigit(ReadChar())) { x = x * 10 + (ReadChar() - '0'); } return f ? -x : x;}
结构体定义：Node 结构体用于线段树存储区间信息，包括左端点、右端点和区间长度。
线段树构建：build 函数初始化线段树，递归构建左右子树，直到叶子节点。
查询操作：query 函数查找区间中的第k小的位置，适用于逆序处理和动态维护队列位置。
主函数：读取输入数据，初始化线段树，逆序处理每个人，查询并记录最终位置，更新线段树，最后输出结果。
通过这种方法，我们可以高效地解决队列排序问题，确保在大规模数据下也能快速得到结果。
转载地址：http://hdxfk.baihongyu.com/