题目描述
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行是按字典序排列的下一个排列。
输入输出样例
样例输入 #1
复制
8
2 6 4 5 8 1 7 3样例输出 #1
复制
8227
2 6 4 5 8 3 1 7
分析：
对于该问题呢，主要难点有两个，一个是如何计算给定的数列是第几个，另一个就是计算它的下一位是多少。
对于第一个问题呢，我们很容易想到dfs来全排列对吧，但是数据给到了20，如果你想要去算20个数的全排列可能会超时，所以我们只能在数学方面想办法优化。那么怎么写呢，我们可以看到这些全排列的数列是按照大小来排序的，那也是不是就是说只要我们求出比给定的这个数列小的数列有几个是不是就可以算出来了呢。OK，开始分析：
我们以样例给定的数列为例子 2 6 4 5 8 1 7 3，我们先看第一位，第一位是2，那么是不是所有以1开头的数都比2小啊，那以1开头的数有多少个呢，答案1：是1*7！；
好了我们看完了第一位是1，如果第一位是2，想得到比给定数列小的数是不是只能让第二位比给定的数列的数小啊，我们可以看到第二位数字是6，那么就是说第二位的数字可以是1,2,3,4,5但是我们的第一位这个时候已经是2了，（这是一个很重要的地方）所以第二位只能是1,3,4,5，OK我们可以得到答案2：4*6！；
同理我们看第三位数，前边两位数只能是2 6，给定的数列第三位是4，那么第三位是不是只能是1,2,3，同理因为前两位定住了是2,6那么第三位只能是1,3；得到答案3： 2*5！
......
最后吧答案n加起来即可
经过一顿分析，我们可以看出其中的规律，对给定的数列每一位数进行分析，答案就是在这个位置往后找有几个数比他小我们记作n，（为什么往后找比她小的数呢，因为在他前边的数都是已经定住了，如果再选用的话会重复）这个数往后有几个空位置我们看作m，那么其中一个答案就是n*m！；最后把所有的数加起来就是结果。
对于第二个问题，如何求解下一个数列，说白了就是求一个比它大的数列s，而且s数列减去给定的数列的结果最小（就是比它大的最小数列）；我们可以通过交换数列的位置来得到。分析一下，是不是我们要尽可能保证两个数列前边的数一样，越是往后的数不同，他们的差值是不是就越小，举个例子 ，对于 2 6 4 5 8 1 7 3 我们要交换的话，肯定是希望3和1交换而不是希望2和3交换，因为我们尽可能保证前边的高位数次序不变。那么怎么实现呢？
我们可以倒序遍历，在倒序的过程当中我们寻找这个数的后边有没有比他大的数，找到那个比它大的最少的交换位置。这样就OK了吗？nonono...我们还要把这个数往后所有的数从小到大再给他排序一遍，为啥呢？请看VCR：
对于例子2 6 4 5 8 1 7 3 我们按着我们分析的来，
倒序查找，先找3，3后边有比他大的数吗？好像没有...
再往前找到了7，7后边有比他大的数吗？好像没有...
再找1，后边有比他大的数吗？有，7和3，那么到底要和谁换位呢？我们上边说了，要和比它大的最少的那个数换位，那肯定就是3了对吧，OK换就完了 2 6 4 5 8 3 7 1，这就完了？和答案不一样啊！对，我们还要把3后边所有的数给他排序一遍（可以借助sort）就得到了 2 6 4 5 8 3 1 7 ！！
OK！上代码！
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int arr[21],brr[21];
int ans = 0;
int main()
{
cin >> n;
brr[1] = 1;
for (int i = 2; i <= n; i++)
brr[i] = brr[i - 1] * i;//求出n个数的阶乘并记录
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= n; i++)
{
int num=0;//记录对于该点，该点后边有多少个小于他的数
for (int j = i + 1; j <= n; j++)
{
if (arr[j] < arr[i])
num++;
}
ans += num * brr[n-i];
}
cout << ans << endl;
int sign = 0,t=1e9,b;
for (int i = n; i >= 1; i--)
{
for (int j = i + 1; j <= n; j++)
{
if (arr[j] > arr[i])//如果后边有大于标记点的数
{
if (arr[j] < t)//不断更新大于标记点的最小值
{
t = arr[j];
b = j;//记录大于标记点的最小值的下标
}
sign = 1;
}
}
if (sign == 1)//如果后边有大于标记点的数
{
int p;//标记点与最小的大于标记点的数换位
p = arr[i];
arr[i] = arr[b];
arr[b] = p;
sort(arr + i + 1, arr + 1 + n);//排序后边所有的书从小到大
break;
}
}
for (int i = 1; i <= n; i++)
cout << arr[i] << ' ';
return 0;
}