排列的字典序问题
时间： 1ms 内存：64M
描述：
n个元素{1,2,……, n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：
给定n以及n个元素{1,2,……, n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
输入：
输入数据的第1行是元素个数n（n≤20）。接下来的1行是n个元素 {1,2,……, n }的一个排列。
输出：
输出数据的第1行是字典序值，第2行是按字典序排列的下一个排列。
示例输入：
8
2 6 4 5 8 1 7 3示例输出：
8227
2 6 4 5 8 3 1 7提示：
参考答案（内存最优[752]）：
#include<stdio.h>
#include<stdlib.h>
void SWAP(int * a, int * b)
{
long long t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
int n,i,k,j,t,order[100];
int lis,f[100],mid,h;
f[0]=1;
for(i=1;i<=22;i++)
f[i]=f[i-1]*i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&order[i]);
if(n==1) printf("0\n1\n");
else if(n>=2)
{
lis=0;
for(i=0,k=n-1;i<n-1;i++,k--)
{
t=0;
for(j=0;j<i;j++)
if(order[j]<order[i]) t++;
lis+=(order[i]-1-t)*f[k];
}
printf("%d\n",lis);
for(i = n-2; i >= 0; i--)
{
if(order[i] < order[i+1])
{
j = i;
for(k = n-1; k > j; k--)
{
if(order[k] > order[j])
{
mid = j+(n-j)/2;
SWAP(&order[j], &order[k]);
for(j++, h = 1; j <= mid; j++, h++)
SWAP(&order[j], &order[n-h]);
}
}
break;
}
}
for(i=0; i < n-1; i++)
printf("%d ",order[i]);
printf("%d",order[i]);
}
}
return 0;
}
参考答案（时间最优[0]）：
#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll f(ll n)
{
if(n==1)return 1;
return n*f(n-1);
}
int get_th(int s[],int n) // 数组中第一个数在所有数里排第几 最小是0
{
int x=0;
for(int i=1;i<n;i++)
{
if(s[i]>s[0])x++;
}
return n-x-1;
}
bool dj(int s[],int n)
{
for(int i=1;i<n;i++)
{
if(s[i]>s[i-1])return false;
}
return true;
}
void sort1(int s[],int n)
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(s[i]>s[j])
swap(s[i],s[j]);
}
}
}
void swap_(int s[],int n)
{
int key=s[0];
int min;
bool first=true;
for(int i=1;i<n;i++)
{
if(s[i]>key)
{
if(first)
{
first=false;
min=i;
}
else
{
if(s[i]<s[min])min=i;
}
}
}
swap(s[0],s[min]);
}
int main()
{
int n;
int i;
cin>>n;
int s[21]; // 排序完的顺序
for(i=0;i<n;i++)
{
cin>>s[i];
}
ll num=0;
for(i=0;i<n-1;i++)
{
int k=get_th(&s[i],n-i);
num= num + k*f(n-i-1);
}
cout<<num<<endl;
for(i=n-2;i>=0;i--)
{
if(dj(&s[i],n-i))continue;
swap_(&s[i],n-i);
sort1(&s[i+1],n-i-1);
break;
}
for(i=0;i<n;i++)
cout<<s[i]<<" ";
cout<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。