本文共 1933 字，大约阅读时间需要 6 分钟。

$a$数组是$1$递增到$k$,然后递减到$k-(n-k)$

实际上数组的后$2n-2k+1$个元素以$k$为中心都是对称的

逆序对个数为$2\ast [1+2+3...+(n-k-1)]+(n-k)$

化简得到逆序对数量为$(n-k{)}^2$

然后看最后$b$数组的形式,必然是

$a[p_1]a[p_2]...a[p_{k-(n-k)}]...a[p_k]...a[p_{k-(n-k)}]$

暂时只观察后面一段长$2n-2k+1$个对称的数字,设$sum=2n-2k+1$

好,现在来证明$p$的后$sum$个对称数字的逆序是固定的

不妨把后面一段对称的数字写成这样的形式比较直观,下面$zh{i}_i$是互不相同的数

$zh{i}_{1}zh{i}_2...zh{i}_{n-k+1}...zh{i}_{2}zh{i}_1$

只考虑每个数作为逆序对的前一个数产生的贡献

设第一大的数在第$i{d}_1$个位置和$sum-i{d}_1+1$个位置

第$i{d}_1$个位置和后面形成$sum-i{d}_1-1$个逆序对

第$sum-i{d}_1+1$个位置和后面形成$i{d}_1-1$个逆序对

总共形成$sum-2$个逆序对,发现和$i{d}_1$并没有关系

对于第二大的数在$i{d}_2$位置,这里需要分$i{d}_1$在$i{d}_2$两端讨论一下,不过结果都是形成$sum-4$个逆序对

所以后面对称部分内部的逆序对是$\sum _{i=1}^{n-k}(sum-2\ast i)=(n-k{)}^2$

惊人的发现!!!仅仅是对称部分,不管$p$数组是什么样,逆序对都已经和$a$一样了

意味着前面不对称的部分,也就是当$i\in [1,n-sum]$时不能和后面产生任何的逆序对,也就是$p_i=i$

而当$i\in [n-sum+1,n]$时,反正怎么放都会产生$(n-k{)}^2$个逆序对,$p$数组干脆从大到小放。

至此问题得到解,很遗憾没有在比赛中写出来,也不想去找规律

能够这么巧妙地自己证明出来,我觉得非常开心.

#include 
   
    using namespace std;const int maxn = 2e5+10;int n,k;int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n >> k;		int sum = 2*n-2*k+1;		for(int i=1;i<=n-sum;i++)	cout << i << " ";		for(int i=k;i>n-sum;i--)	cout << i << " ";		cout << endl;	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112670071 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！