题解 P1338 【末日的传说 】

# 咱这规律找滴彳亍不彳亍  --------------------------------- 这个表是通过暴力枚举打的表，最左一列数字是逆序对个数，右边的是对应的字典序最小的排列，即所求答案 现在可以来研究一下为什么会产生这种规律 首先考虑一个特殊情况，当逆序对个数为m\*(m-1)/2时，一个长度为m的递减序列就可以完成 在递增序列的基础上，若使字典序最小，肯定尽可能只变动后面的数字，当逆序对个数为m\*(m-1)/2时，只将后m个数字倒序排列是最优的 因此就出现了图中粉色部分和黄色部分，当逆序对个数位于(m-1)\*(m-2)/2和m\*(m-1)/2之间时，只对后m个数字重排列 那么如果逆序对个数为m\*(m-1)/2+1，此时就不能只变动后m个数字，从右往左第m+1个数字必须发生变化 若使字典序最小，因为前n-m-1个数字不变，则第n-m个（即从右往左第m+1个）数字应尽量小，而它又必须比n-m大（原来是n-m） 因此此数字至少应该是n-m+1 后m个数字中，比n-m+1小的只有n-m一个，因此n-m+1只能提供一组逆序对，还需要m\*(m-1)/2个逆序对 因此剩下的m个数字必须呈降序排列 如果逆序对个数继续增加到m\*(m-1)/2+2，则第n-m个数字为n-m+1也无法满足需求，因为后m个数字是降序的，已经达到最大逆序对 因此第n-m个数字必须再次增加，变为n-m+2 此时后m个数字中比n-m+2小的有n-m和n-m+1两个，还需要m\*(m-1)/2个逆序对，于是后m个数字又必须降序排列…… 依此类推，每当逆序对个数+1，第n-m个数字就+1，这就形成了图中的红色部分 剩余的数字降序排列，形成图中黄色和蓝色部分 其中蓝色部分比红色部分大，黄色部分比红色部分小 ---------------------------- 研究过规律的原理后，便可以找到一种正推出做法的思路（而不是靠打表观察或灵稽一动） 当逆序对个数为0时，序列为递增序列，若逆序对个数+1，则交换最后两个数 接下来再让逆序对+1，变为2，从左至右考虑每一位数字是否有必要改变 结果发现倒数第3个数字不得不发生变化，因为后2个数字为降序排列 于是让倒数第3个数字+1，变成n-1，然后发现n-1只能和n-2组成一组逆序对，还有2-1=1个逆序对需要解决 而1=2*(2-1)/2，因此后2个数必须为降序，由此得到逆序对个数为2的解 再让逆序对+1，因为后2个数必须为降序，所以倒数第3个数不得不变化 让倒数第3个数字+1，变成n-2…… 类推上述步骤即可发现规律与构造方法 --------------------- 代码： ```cpp #include<iostream> #include<cstdio> using namespace std; int n,m; int main(){ cin>>n>>m; int b=0; for(b=0;b<n && m>b;++b) m-=b; for(int i=1;i<=n-b-1;++i) printf("%d ",i); printf("%d ",n-(b-m)); for(int i=1,j=n;i<=b-m;++i,--j) printf("%d ",j); for(int i=1,j=n-(b-m)-1;i<=m;++i,--j) printf("%d ",j); cout<<endl; return 0; } ```