Uim的情人节礼物·其之壱
题目描述
情人节到了，Uim打算给他的后宫们准备情人节礼物。UIm一共有N（1<=N<=9）个后宫妹子（现充去死 挫骨扬灰!）。
为了维护他的后宫的稳定。他通过编程，得出了一个送礼物的最佳顺序。这个我们管不着。
然而他认为，如果什么事情做得太圆满不是什么好事。于是他希望得到 原定顺序 的 前一个字典序的序列。
输入输出格式
输入格式：
第一行一个整数N
第二行N个整数，表示原定排列
输出格式：
前一个排列
输入输出样例
输入样例#1：
3
1 3 2
输出样例#1：
1 2 3
说明
若当前排列已经是第一个，则输出'ERROR'（引号不输出）
分析：
很多大佬都是用$STL$的$prev\_permutation$做的，甚至有大佬搜索、模拟各种奇妙算法过。
这里博主用的是康托展开和逆康托展开。
非常容易，对于给定的排列，求出其康托展开值$m$，然后再求$m-1$的逆康托展开。
Code：
//It is made by HolseLee on 8th Oct 2018
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int n,m,f[],a[];
char ka[];
vector<int>v; inline int cantor()
{
int ret=,x;
for(int i=; i<n; ++i) {
x=;
for(int j=i+; j<n; ++j)
if( (ka[i]-ka[j])> ) x++;
ret+=x*f[n-i-];
}
return ret;
} inline void incantor(int k)
{
int x;
while( !v.empty() ) v.erase(v.end());
for(int i=; i<=n; ++i) v.push_back(i);
for(int i=; i<n; ++i) {
a[i]=v[(x=k/f[n-i])];
v.erase(v.begin()+x);
k%=f[n-i];
}
a[n]=v[];
} int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=; i<n; ++i) cin>>ka[i];
f[]=;
for(int i=; i<=; ++i) f[i]=f[i-]*i;
incantor(cantor()-);
for(int i=; i<=n; ++i) printf("%d ",a[i]);
return ;
}