贪心Sorted Adjacent Differences

题目描述：
You have array of n numbers a1,a2,…,an.

Rearrange these numbers to satisfy |a1−a2|≤|a2−a3|≤…≤|an−1−an|, where |x| denotes absolute value of x. It's always possible to find such rearrangement.

Note that all numbers in a are not necessarily different. In other words, some numbers of a may be same.

You have to answer independent t test cases.

Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains single integer n (3≤n≤105) — the length of array a. It is guaranteed that the sum of values of n over all test cases in the input does not exceed 105.

The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109).

Output
For each test case, print the rearranged version of array a which satisfies given condition. If there are multiple valid rearrangements, print any of them.

Example
Input
2
6
5 -2 4 8 6 5
4
8 1 4 2
Output
5 5 4 6 8 -2
1 2 4 8
Note
In the first test case, after given rearrangement, |a1−a2|=0≤|a2−a3|=1≤|a3−a4|=2≤|a4−a5|=2≤|a5−a6|=10. There are other possible answers like "5 4 5 6 -2 8".

In the second test case, after given rearrangement, |a1−a2|=1≤|a2−a3|=2≤|a3−a4|=4. There are other possible answers like "2 4 8 1".
我写的一直wrong answer

#include<iostream>
#include<algorithm>
#define MAX 100000 
using namespace std;
int n;
int Search(int a[],int h){
    //int cha=MAX;
    int i=h-1,j=h+1;
    while(i>=0){
        if(a[i]==MAX)i--;
        else break;
    }

    while(j<n-1){
        if(a[j]==MAX)j++;
        else break;
    }

    int num=abs(a[h]-a[i])<abs(a[h]-a[j])?i:j;
    a[h]=MAX;
    return  num;

}
int main(){
    int t,h,l;
    cin>>t;
    while(t--){
        cin>>n;
        int *a=new int[n];
        int *b=new int[n];
        int i;
        for(i=0;i<n;i++){
            cin>>a[i];
            //cout<<a[i];
        }
        sort(a,a+n);
        int cha=MAX;
        for(i=0;i<n-1;i++){//找到开头元素 
            if(abs(a[i+1]-a[i])<cha){
                h=i+1;l=i;
                cha=abs(a[i+1]-a[i]);
            }
        }
        int j=0;
        b[j++]=a[l];
    //    cout<<a[l]<<endl;
        b[j++]=a[h];
        //cout<<a[h]<<endl;
        a[l]=MAX;
        while(j<n){
        //    cout<<"hello";
            h=Search(a,h);//找到与a[h]绝对值差值最小的 坐标 
        //    cout<<"h is"<<h<<endl;
            b[j++]=a[h];
            //a[h]=MAX;
        }
        for(i=0;i<n-1;i++){//打印出来 
            cout<<b[i]<<" ";
        }
        cout<<b[i]<<"\n";
    }
}

正确的版本

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;

const int maxn = 100000 + 10;
int a[maxn];
int main() {
    int t;
    int n;
    scanf("%d", &t);
    while (t--) {
        stack<int> s;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        sort(a, a + n);
        int i = 0;
        int j = n - 1;
        int cnt = 0;
        while (i <= j) {
            if (!cnt) {
                s.push(a[j]);
                j--;
                cnt = 1;
            }
            else {
                s.push(a[i]);
                i++;
                cnt = 0;
            }
        }
        int t = s.top();
        printf("%d", t);
        s.pop();
        while (s.size() != 0) {
            t = s.top();
            printf(" %d", t);
            s.pop();
        }
        printf("\n");
    }

    return 0;
}