这一个题目涉及到的算法是:逆康托展开
第几是谁?
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 现在有"abcdefghijkl”12个字符,将其按字典序排列,如果给出任意一种排列,我们能说出这个排列在所有的排列中是第几小的。但是现在我们给出它是第几小,需要你求出它所代表的序列.
- 输入
- 第一行有一个整数n(0<n<=10000);
随后有n行,每行是一个整数m,它代表着序列的第几小; - 输出
- 输出一个序列,占一行,代表着第m小的序列。
- 样例输入
-
3 1 302715242 260726926
- 样例输出
-
abcdefghijkl hgebkflacdji gfkedhjblcia
#include <iostream> #include <cstring> #include <map> using namespace std; struct BB { int Num; int flag; }b[15];//b数组用来标记 int a[15],c[15]; int JC(int x)//求阶乘的函数 { int num=1; while(x) { num*=x; x--; } return num; } int main() { map<int,char> m;//定义一个map容器,以便后边把数字转化为字母 for(int k=0;k<=11;k++) m[k+1]=char('a'+k); int n; cin>>n; while(n--) { memset(a,0,sizeof(a)); int N,num,i,j,A=1,JS; cin>>N; num=N-1; for(i=1;i<=12;i++) {b[i].Num=i;b[i].flag=0;} for(i=11;i>=1;i--)//逆康托展开 { a[A]=num/JC(i); A++; num=num%JC(i); } int C=0,sum; for(i=1;i<12;i++) { JS=-1;sum=0; for(j=1;j<=12;j++) { sum++; if(b[j].flag==0) JS++; if(JS==a[i]) break; } c[C]=sum; b[c[C]].flag=1; C++; }//计算出排在第i位的数在1~12中的哪一个? for(i=1;i<=12;i++) if(b[i].flag==0) { c[C]=i;C++;break; }//把最后一位数补上 for(i=0;i<C;i++) cout<<m[c[i]];//把1~12转化为a~l; cout<<endl; } return 0; }
康托展开和逆康托展开的算法链接:点击打开链接