2023-08-08 22:58:04 solution
思路:
考虑到一个最小值对答案的贡献,发现如果是序列最小值,因为配对了 \(n-1\) 次,而每次配对的结果都是它,所以在 \(b\) 中会出现 \(n-1\) 次。
同理,次小值(可能与最小值相同)出现 \(n-2\) 次,第三小出现 \(n-3\) 次等。因为保证有解,所以我们只需要给 \(b\) 数组排好序后跳相应的步数并且输出当前数即可,最后注意 \(a\) 数组最大值只需要大于等于 \(b\) 数组最大值即可,这里我出于方便直接取等了。
\(Code\)
int T,n,m,a[1000006];
int main(){
for(T=read();T--;){
n=read();
m=n*(n-1)>>1;
for(int i=1;i<=m;i++){
a[i]=read();
}
sort(a+1,a+1+m);
int o=0;
for(int i=1;i<=m;i+=n-o){
printf("%d ",a[i]);
o++;
if(i==m){
printf("%d\n",a[i]);
break;
}
}
}
}