1815: 蓝桥杯2014年第五届真题-排列序数

解题思路:

思路1：暴力排列，运用STL中的next_permutation函数

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin>>s;
    string str=s;
    unsigned int res=0;
    sort(s.begin(),s.end());
    do {
        if(s==str)    break;
        res++;
    }while(next_permutation(s.begin(),s.end()));
    printf("%u",res);
    return 0;
}

思路2：康托展开

康托展开_百度百科

阶乘可以打一个表，也可写一个函数

#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
int fac[12]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800};
//寻找比当前元素更小的且在后面的元素 
int smaller(string s,int index) {
    int res=0;
    for(int i=index;i<s.length();i++) {
        if(s[i]<s[index])   res++;
    }
    return res;
}

int main(){
    string s;
    cin>>s;
    int len=s.length(),res=0,sum=0;
    for(int i=0;i<len;i++) {
        sum=smaller(s,i);
        res+=sum*fac[len-i-1];
    }
    printf("%d",res);
    return 0;
}