程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ139 我排第幾個（字符串的解碼）

NYOJ139 我排第幾個（字符串的解碼）

編輯：C++入門知識

NYOJ139 我排第幾個（字符串的解碼）

現在有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;
}