题目链接：https://www.luogu.org/problemnew/show/P1338
不水，不水了。。。
大约一月前学了一下康托展开，初赛就考到了，看看分数，要是没学初赛就过不去了！！！
所以看到排列，我自然而然想到救过命的康托展开，但是尝试发现，是行不通的，包括next_permutation和手写一个生成排列的程序。
没办法，看题解吧，居然是O(n)的做法，本来还以为要再带上点东西的。
我们每次考虑未放过的最小的数，假如他放在从左往右第一个位置，那么剩下的最大可能产生逆序对数必须小于等于m，否则，他一定不会放在第一个位置，不管他放在哪，因他而产生的逆序对数是确定的，就是他之前空的位置。而这个数放得越靠后，剩下序列的剩下序列的逆序对数也就越少，因此其字典序也就越小，剩下的自然在最后一个位置的前面，这样最终答案的字典序也就越小，所以我们要放到最后一个位置。
1 #include <cstdio> 2 3 typedef long long ll; 4 5 const int maxn = 5e4 + 5; 6 7 int p[maxn]; 8 9 int main() { 10 int n, m; 11 scanf("%d%d", &n, &m); 12 ll s = 1, t = n; 13 for (int i = 1; i <= n; ++i) { 14 if (m <= (n - i - 1LL) * (n - i) / 2) p[s++] = i; 15 else m -= t - s, p[t--] = i; 16 } 17 for (int i = 1; i <= n; ++i) printf("%d ", p[i]); 18 return 0; 19 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9795004.html
