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
", p);
Update(1, p, 0);
}
}
return 0;
}
上一篇 談談分布式計算的算子層
下一篇 內存問題排查手段及相關文件介紹
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
