首页 > 代码库 > UVA 11525 - Permutation(树状数组)
UVA 11525 - Permutation(树状数组)
UVA 11525 - Permutation
题目链接
题意:给定一个k个数字,求第n个全排列,由于n很大,输入的方式为∑k1Si?(K?i)!
思路:全排列,很容易看出,前面的si对应的就是数组中第k小的数字,那么问题变成每次找第k小的数字,然后去掉这个数字,这个用树状数组很容易实现
代码:
#include <cstdio> #include <cstring> #define lowbit(x) (x&(-x)) const int N = 50005; int t, k, bit[N]; void add(int x, int v) { while (x <= k) { bit[x] += v; x += lowbit(x); } } int get(int x) { int ans = 0, num = 0; for (int i = 16; i >= 0; i--) { ans += (1<<i); if (ans >= k || bit[ans] + num >= x) ans -= (1<<i); else num += bit[ans]; } return ans + 1; } int main() { scanf("%d", &t); while (t--) { memset(bit, 0, sizeof(bit)); scanf("%d", &k); for (int i = 1; i <= k; i++) add(i, 1); int num; for (int i = 1; i <= k; i++) { scanf("%d", &num); num++; int v = get(num); printf("%d%c", v, i == k ? '\n' : ' '); add(v, -1); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。