我们知道1——k有K！种排列，现在给定k和n，要你按字典序输出 第n种排列的数列
而且题目给的 n是 n=S1（k-1）！+S2(k-2)!+...+Sk-1*1!+Sk*0!(0=<Si<=k-i),
k最大为50000，直接算出来不可能，我发现这个n的表达式很有意思，明显（k-1）！就是表示第一次除第一个以外，剩下k-1个数的排列个数，乘一个S1就说明之前用了多少次这种排列了，根据这个 再手算了一下，发现就是，每次找第Sk个数，输出，当然已经访问过的数就要T出去
这很明显就是树状数组 （或者线段树的单点修改和查询）功能，先初始化每个都是大小为1，然后每次二分找第Sk个，找到之后，把该位置置为-1，消除该位的影响，继续找，继续输出即可。你看题目里给定的S的范围也就是顺应这个，故意把剩下几个数，S就恰好限定在这个里面
发现自己二分写的还不是很熟，一开始还搞了一下子，是用mid还是L做结果呢 最后在我的写法里被证明是用L做结果
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 50000+10 using namespace std; int A[N]; int n; int lowbit(int x) { return x&(-x); } void add(int x,int v) { while (x<=n){ A[x]+=v; x+=lowbit(x); } } void init() { for (int i=1;i<=n;i++){ add(i,1); } } int query(int x) { int ret=0; while (x>0){ ret+=A[x]; x-=lowbit(x); } return ret; } int main() { int t; scanf("%d",&t); while (t--) { scanf("%d",&n); init(); for (int i=1;i<=n;i++){ int a; scanf("%d",&a); int L=1,R=n,mid; while (L<R) { mid=(L+R)>>1; int tmp=query(mid); //if (tmp==a+1) break; if (tmp<a+1) L=mid+1; else R=mid; } //cout<<"@@"<<mid<<endl; add(L,-1); printf("%d",L); if (i<n) putchar(' '); } puts(""); } return 0; }