题解 P1338 【末日的传说 】

2020-02-03 17:18:51


咱这规律找滴彳亍不彳亍


这个表是通过暴力枚举打的表,最左一列数字是逆序对个数,右边的是对应的字典序最小的排列,即所求答案

现在可以来研究一下为什么会产生这种规律

首先考虑一个特殊情况,当逆序对个数为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……

类推上述步骤即可发现规律与构造方法


代码:

#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;
}