题意: 给定一个长度为$n$的序列$a$,最大值为$k$,
$a=\{1,2,3,…,k,k-1,…\ ,k-(n-k)\}$
现在需要你构造一个长度为$k$的排列$p$,序列$b[i]=p[a[i]]$ ,保证$b$的逆序对数不多于$a$的逆序对数,且$p$的字典序尽可能大。
数据范围:$1\leq k\leq 10^5,k\leq n\leq 2k$
题解:
$b$序列分为以下两部分:
$1. \ p[1],p[2],…\ ,p[k-(n-k)-1]$
$2. \ p[k-(n-k)],…\ ,p[k-1],p[k],…\ ,p[k-(n-k)+1],p[k-(n-k)]$
第$2$部分中,不重复的数为:
$p[k-(n-k)],p[k-(n-k)+1],…\ ,p[k-1],p[k]$
这些数中选取任意两个都可以在第$2$部分中得到一个逆序对,所以在第$2$部分中逆序对数是确定的,故序列$a$第$2$部分和序列$b$第$2$部分的逆序对数一样,只需要去考虑第$1$部分的问题了。
第$1$部分内部$a$序列的逆序对数为$0$,且其相对于后面部分的逆序对数也是最少的,因为所有小的数都在前面,故第$1$部分内部$b$序列必须是升序的,且必须是 都为$[1,k]$中最小的,所以第$1$部分内部$b$序列为$[1,k-(n-k)-1]$。
- 按照$b$的第$1$部分构造$p$的第$1$部分:$[1,k-(n-k)-1]$
- 按照$b$的第$2$部分构造$p$的第$2$部分:由于内部的逆序对数确定,要求$p$字典序最大,
故将$[k-(n-k),k]$逆序放置即可。
代码:
#include<bits/stdc++.h>
int n, k, T;
int main()
{
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
for(int i = 1, a = 1, b = k; i <= k; ++i) {
if(i < 2 * k - n) printf("%d", a++);
else printf("%d", b--);
printf("%c", " \n"[i == k]);
}
}
return 0;
}