蓝桥杯——排列序数

时间:2021-05-02 11:12:15
标题:排列序数


   如果用a b c d这4个字母组成一个串,有4!=24种,如果把它们排个序,每个串都对应一个序号:
  abcd  0
  abdc  1
  acbd  2
  acdb  3
  adbc  4
  adcb  5
  bacd  6
  badc  7
  bcad  8
  bcda  9
  bdac  10
  bdca  11
  cabd  12
  cadb  13
  cbad  14
  cbda  15
  cdab  16
  cdba  17
  ...


    现在有不多于10个两两不同的小写字母,给出它们组成的串,你能求出该串在所有排列中的序号吗?


【输入格式】
一行,一个串。


【输出格式】
一行,一个整数,表示该串在其字母所有排列生成的串中的序号。注意:最小的序号是0。


例如:
输入:
bdca


程序应该输出:
11


再例如:
输入:
cedab


程序应该输出:
70


资源约定:
峰值内存消耗 < 256M
CPU消耗  < 1000ms




请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。


所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。


注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。


提交时,注意选择所期望的编译器类型。

分析:将输入的字符串进行全排列,按字典序进行排序编号并存在string型数组中,然后遍历string数组,相同则输出该数组的下标即可

代码:

#include <iostream>#include <algorithm>
#include <string>
#include <string.h>
char ch[15];
using namespace std;
int f(int x)//求阶乘
{
if(x==1)
return 1;
return f(x-1)*x;
}
string a[3700000];//10的阶乘为3628800
int main()
{
cin>>ch;
string q=(string)ch;
int len=strlen(ch);
int maxx=f(len);//最大编号
//cout<<len<<' '<<maxx<<endl;
int i=0;
sort(ch,ch+len);//重要!!!
do
{
a[i++]=(string)ch;
}while(next_permutation(ch,ch+len));
for(int j=0;j<maxx;j++)
{
if(a[j]==q)
{
cout<<j;
return 0;
}
}
return 0;
}

样例数据:

蓝桥杯——排列序数

蓝桥杯——排列序数

边界数据:

蓝桥杯——排列序数

思路二:只需要遍历字符串中的每一个字符,然后找出每个字符后面有多少个比它小的,也就是逆序的,然后乘以后面字符个数的阶乘,每一步的结果相加即可。

#include<iostream>#include<cstring>using namespace std;int a[20];int main(){    a[1]=1;    for(int i=2;i<13;i++)    {        a[i]=a[i-1]*i;    }    char str[15];    cin>>str;    int len=strlen(str),index=0,num;    for(int i=0;i<len;i++)    {         num=0;        for(int j=i+1;j<len;j++)        {            if(str[j]<str[i])            {                num++;            }        }        index+=num*a[len-1-i];    }    cout<<index<<endl;    return 0;}

第二种解法更好一点。