B. Sorted Adjacent Differences(思维构造)

\(给出n个数字，要求构造一个由这n个数组成的序列，使得|a_1-a_2|<=|a_2-a_3|...<=|a_{n-1}-a_n|\)

\(排序后，从数列中间取个数，然后从左右分别循环取数，这样保证差值递增\)

\(还是很巧妙地.\)

#include <bits/stdc++.h>

using namespace std;

int t,n,a[100009];

int main()

{

	cin>>t;

	while(t--)

	{

		cin>>n;

		for(int i=1;i<=n;i++)	cin>>a[i];

		sort(a+1,a+1+n);

		cout<<a[(n+1)/2]<<" ";

		int l=(n+1)/2-1,r=(n+1)/2+1,ok=0;

		while(1)

		{

			if(ok==0)	cout<<a[r++]<<" ",ok=1;

			else	cout<<a[l--]<<" ",ok=0;

			if(r==n+1&&l==0)	break;

		}

		cout<<endl;

	}

}

巴特西

B. Sorted Adjacent Differences(思维构造)

最新文章

热门文章