首页 > 代码库 > UVA11525 - Permutation(线段树)
UVA11525 - Permutation(线段树)
UVA11525 - Permutation(线段树)
题目链接
题目大意:给定一个K,将数字1-K这个序列全排列(K!种),然后给你一个公式让你求的N,问第N小的数字排列。
解题思路:因为这个求N的公式很特别,Si(K - i)!这个其实就是确定了第i个数是第(Si + 1)大的数字。例如K = 3, S序列 3 2 1,那么3 (3 - 1)!就说明第一个数是3。接着2 (2 - 1)!说明第二个数是2(因为3已经用了)。所以这题是要查询第(si + 1)大的数,并且需要将用过的数更新。
代码:
#include <cstdio>
#include <cstring>
const int N = 5e4 + 5;
#define lson(x) (2*(x))
#define rson(x) (2*(x) + 1)
struct Node {
int l, r, v;
void set(int l, int r, int v) {
this->l = l;
this->r = r;
this->v = v;
}
}node[4 * N];
void build (int u, int l, int r) {
if (l == r)
node[u].set(l, r, 1);
else {
int m = l + (r - l) / 2;
build(lson(u), l, m);
build(rson(u), m + 1, r);
node[u].set(l, r, node[lson(u)].v + node[rson(u)].v);
}
}
int Query (int u, int k) {
if (node[u].l == node[u].r)
return node[u].l;
if (k > node[lson(u)].v)
return Query(rson(u), k - node[lson(u)].v);
else
return Query(lson(u), k);
}
void Update (int u, int p, int v) {
if (node[u].l == node[u].r)
node[u].v = v;
else {
int m = node[u].l + (node[u].r - node[u].l) / 2;
if (p <= m)
Update (lson(u), p, v);
else
Update (rson(u), p, v);
node[u].v = node[lson(u)].v + node[rson(u)].v;
}
}
int main () {
int T, K, num, p;
scanf ("%d", &T);
while (T--) {
scanf ("%d", &K);
build(1, 1, K);
for (int i = 0; i < K; i++) {
scanf ("%d", &num);
p = Query (1, num + 1);
if (i != K - 1)
printf ("%d ", p);
else
printf ("%d\n", p);
Update(1, p, 0);
}
}
return 0;
}
UVA11525 - Permutation(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。