No More Inversions 全网最详细 回文序列的逆序对

传送门：http://codeforces.com/contest/1473/problem/C

题意

　　给定n、k，a数组为1 2 3...k-1,k,k-1,...k-(n-k)，要求构造一个长度为k的排列(1到k每个数出现一次)，同时b[i]=a[p[i]]。要求b里面的逆序对不多于a里面的逆序对且字典序最大。

前提(回文序列的逆序对恒定)

　　在解决这个问题之前，首先我们来看这样一个序列 s1 s2 ... sk ... s2 s1，也就是回文序列

　　这个序列关于sk对称，我们需要知道的是，只要si互不相等，序列的逆序对就是相同的

　　因为序列的取值为[s1,sk]，那么任取两个数x和y，我们都能找到形如y...x...x...y或者y...x...y的分布

　　例如在1 2 3 2 1 中，对于x=2，y=1我们可以找到1...2...2...1，对于x=3，y=2我们可以找到2...3...2

　　我们可以发现，无论x大还是y大，y...x...x...y贡献了两个逆序对，y...x...y贡献了一个逆序对

　　所以这个序列的逆序对数为2*C(2,k-1)+k-1=(k-1)²

思路

　　我们把a数组分为两部分：

　　•1 2 3 4 ... k-(n-k)-1

　　•k-(n-k) k-(n-k)+1 ... k k-1 ...k-(n-k)

　　我们可以知道的是逆序对都出现在第二部分，对于b[i]=p[a[i]]来说，与a数组对应，我们也可以把b数组分为两部分：

　　•a[p[1]]  a[p[2]] ... a[p[k-(n-k)-1]]

　　•a[p[k-(n-k)]]  a[p[k-(n-k)+1]] ... a[p[k]] ...a[p[k-(n-k)]]

　　我们可以发现，a数组和b数组的第二部分，均是前提中描述的序列，也就是说，a数组和b数组的第二部分的逆序对数是一样的！

　　而a数组的第一部分是没有逆序对的，回到我们这个问题，现在无论我们怎么构造，b数组的第二部分的逆序对数已经和a数组一样了，所以b数组的第一部分不能产生新的逆序对，也就是说b数组的第一部分也要是递增的。

　　我们再来看b数组的第二部分，此时不用管逆序对了，怎么才能让b数组的字典序最大呢——对于一个回文序列来说，自然是形如3 2 1 2 3的字典序最大。设置p数组为k k-1...k-(n-k)即可将a数组由凸转向凹，由形如1 2 3 2 1转化为3 2 1 2 3。

　　我们再来看b数组的第一部分，第二部分已经将k-(n-k)到k的取值用了，所以第一部分的取值只能为1到k-(n-k)-1，上文提到只能是递增的，所以p的前半部分也就确定了为1到k-(n-k)-1

结论

　　p数组第一部分为1...k-(n-k)-1，当k-(n-k)-1<=0时第一部分为空

　　第二部分为 k k-1 k-2 ... k-(n-k)

AC代码

#include<iostream>
using namespace std;
int t,n,k;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=k-(n-k)-1;i++){
            cout<<i<<" ";
        }
        for(int i=k;i>=k-(n-k);i--){
            cout<<i<<" ";
        }
        cout<<'
';
    }
    return 0;
}