11525 – Permutation（二分+树状数组）
最后更新于：2022-04-01 15:53:41
题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=502&problem=2520&mosmsg=Submission+received+with+ID+16730468)
题意：从1~k的所有排列中找到第n个排列， n由公式给出。
思路：可以发现， 这个公式就是康托展开公式（康托展开百科：[点击打开链接](http://baike.baidu.com/link?url=iyF_OrLBeETDKSZo-iY8M5MHQeJ0UZLkczMNtJ0t61rr-mpn_rHa0qeMlmHfv252mRIQIu7OEw6ldXVriCCDZ_)）。 那么s[i]的意思就是i个数中当前数排在第几。
如此， 可以用二分+树状数组快速求解， 和一道BC题目神似。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 50000 + 10;
int T,n,v,m,c[maxn];
int sum(int x) {
int ans = 0;
while(x > 0) {
ans += c[x];
x -= x & -x;
}
return ans;
}
void add(int x, int d) {
while(x <= n) {
c[x] += d;
x += x & -x;
}
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
memset(c, 0, (n+1)*sizeof(c[0]));
for(int i=1;i<=n;i++) {
add(i, 1);
}
for(int i=1;i<=n;i++) {
scanf("%d",&v); v++ ;
int l = 1, r = n, m ;
while(r > l) {
m = (l + r)/2;
if(sum(m) >= v) r = m;
else l = m + 1;
}
printf("%d%c", l , i == n ? '\n' : ' ');
add(l, -1);
}
}
return 0;
}
~~~