国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > UVA11525 - Permutation(线段树)

UVA11525 - Permutation(线段树)

来源:程序员人生   发布时间:2014-10-04 08:00:01 阅读次数:3268次

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; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生