NYOJ 139 我排第幾個 - 字符串字典序排名

問題描述

12 個字符 a-l 全排列按字典序排序。給定一個排列，求其排名（1-based）。

算法：逐位計算排名增量

對於位置 i (1-based) 的字符 s[i]，統計其右側有多少字符小於 s[i]，設為 k。則排名增加 k * (12-i)!。累加所有位，最後 +1 得排名。

代碼實現（C++）

#include 
using namespace std;
long long fact[13];

int main() {
    fact[0] = 1;
    for (int i = 1; i <= 12; i++) fact[i] = fact[i-1] * i;
    int T; scanf("%d", &T);
    while (T--) {
        char s[15]; scanf("%s", s+1); // 1-based
        long long rank = 0;
        for (int i = 1; i <= 12; i++) {
            int k = 0;
            for (int j = i+1; j <= 12; j++) if (s[j] < s[i]) k++;
            rank += k * fact[12 - i];
        }
        printf("%lld\n", rank + 1);
    }
    return 0;
}

關鍵點

• 預計算 0! 到 12!。
• 雙層循環 O(12²) 極快。
• 字符比較直接用 ASCII 碼，a-l 連續遞增。