P1338 末日的传说
斯德哥尔摩
2018-10-17 00:37:05
[P1338 末日的传说](https://www.luogu.org/problemnew/show/P1338)
我们考虑把这个问题缩小范围。
比如$n==5$，在决定了最小的数$1$的位置之后，剩下的几个数是$2\ 3\ 4\ 5$，但是具体他们是多少没必要关心，我们只要关心他们的相对大小关系。
所以考虑完当前最小的数，算出这个数对答案的贡献，然后减掉这个贡献，就可以转而解决一个更小的子问题。
即：$n->n-1$
回到题目上，要求是求一个有$m$个逆序对的字典序最小的排列。
我们知道一个长度为$n$的排列最多有$\frac{n(n-1)}{2}$个逆序对，也知道一个排列的逆序对数越多，排列字典序越大。
所以如果当前$m$不比当前的$\frac{(n-1)(n-2)}{2}$（也就是减少一个数之后的最多的逆序对数）大，就可以直接把当前的最小数放在最前面，这肯定是最优的。
反之，则考虑最小数的放置位置。
假设当前排列长为$n$，最小数为$a$，则$a$有$n$种放法，放在从左到右第$i$个位置时会生成$i-1$个逆序对。
因为它左边有$i-1$个比他大。
因为$m$大于$n-1$长度排列最多所能产生的逆序数，所以$a$不可能放在最前面，否则不满足条件。
怎么办呢？
想到之前说的逆序对越多字典序越大，我们就必须让剩下的数能构成的逆序对数尽量小，所以$a$要放到最后，这样$m$减少的最多。
放完了$a$，问题就变成了$n-1$和$m-(\text{a的贡献})$的子问题，递归求解即可。
时间复杂度$O(n)$。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 50010
using namespace std;
int n,m,ans[MAXN];
long long head,tail;
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
n=read();m=read();
head=1;tail=n;
for(int i=1;i<=n;i++){
long long x=1ll*(n-i)*(n-i-1)/2;
if(x>=m)ans[head++]=i;
else{
ans[tail--]=i;
m-=(tail-head+1);
}
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
printf("\n");
}
int main(){
work();
return 0;
}
```