NYOJ139 我排第几个（字符串的解码） - c++编程基础

现在有abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

输入第一行有一个整数n（0 随后有n行，每行是一个排列；输出输出一个整数m，占一行，m表示排列是第几位；样例输入

3
abcdefghijkl
hgebkflacdji
gfkedhjblcia

样例输出

1
302715242
260726926

题目分析：

本题的家吗问题，在《算法入门经典》中有解答，对于每一个字符s，若在其后有k个字符小于s，则当前的序列的排序会增大k*f[12-i]。

AC代码：

 
/**
 *给出一个字符串，仅由a~l组成，每个出现一次，求给出字符串的字典序大小
 *对于每一个字符s，若在其后有k个字符小于s，则当前的序列的排序会增大k*f[12-i]
 *其中f是每个数的阶乘，i为s的位置，因此只需模拟每一位进行比较即可。
 */
#include
     
      
#include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   using namespace std; int main() { long long f[15]; f[1]=1; for(int i=2;i<=12;i++){ f[i]=f[i-1]*i; } char s[15]; int t; scanf(%d,&t); while(t--){ scanf(%s,s+1); long long sum=0; for(int i=1;i<=12;i++){ int k=0; for(int j=i+1;j<=12;j++){ if(s[i]>s[j]) k++; } sum+=f[12-i]*k; } printf(%lld ,sum+1); } return 0; }