problem
A. Mean Inequality
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array a of 2n distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its 2 neighbours.
More formally, find an array b, such that:
b is a permutation of a.
For every i from 1 to 2n, bi≠bi−1+bi+12, where b0=b2n and b2n+1=b1.
It can be proved that under the constraints of this problem, such array b always exists.
Input
The first line of input contains a single integer t (1≤t≤1000) — the number of testcases. The description of testcases follows.
The first line of each testcase contains a single integer n (1≤n≤25).
The second line of each testcase contains 2n integers a1,a2,…,a2n (1≤ai≤109) — elements of the array.
Note that there is no limit to the sum of n over all testcases.
Output
For each testcase, you should output 2n integers, b1,b2,…b2n, for which the conditions from the statement are satisfied.
Example
inputCopy
3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9
outputCopy
3 1 4 2 5 6
123 10 456 789
9 6
Note
In the first testcase, array [3,1,4,2,5,6] works, as it’s a permutation of [1,2,3,4,5,6], and 3+42≠1, 1+22≠4, 4+52≠2, 2+62≠5, 5+32≠6, 6+12≠3.
solution
#include<bits/stdc++.h>
using namespace std;
int a[70];
int main(){
int T; cin>>T;
while(T--){
int n; cin>>n;
int nn = 2*n;
for(int i = 1; i <= nn; i++)cin>>a[i];
sort(a+1,a+nn+1);
for(int i = 1, j = nn; i <= n && j>=n+1; i++, j--){
if(i!=1)cout<<" ";
cout<<a[j]<<" "<<a[i];
}
cout<<"\n";
}
return 0;
}