题目意思
给你一些数,让你把它们按某种顺序排成一圈,使得每个数$ a_i $都满足:
- $a_{i-1} $ < $a_i$ 且 $a_{i+1}$ < $a_i$
或者
$a_{i-1} $ > $a_i$ 且 $a_{i+1}$ > $a_i$
思路
不难发现,一个合格的序列满足"小,大,小,大....大",且元素个数是奇数。那么,我们将所有元素按照从小到大的顺序排序。
接下来把所有元素分成两份,
第一份: $a_1$~$a_{n/2}$
第二份: $a_{n/2+1}$~$a_n$
接下来按照 第一份的第一个,第二份的第一个,第一份的第二个,第二份的第二个......这样的顺序排,就可以的出答案了。
最后再判断一下刚才排出来的序列是否合法就行了。
最后贴上代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=200010;
int t,n,a[maxn],tot,ans[maxn];
bool cmp(int x,int y){return x>y;}
int main(){
scanf("%d",&t);
while(t--){
bool flag=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
if(n%2==1){printf("NO\n");continue;}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(i%2)ans[i]=a[i/2+1];
else ans[i]=a[n/2+i/2];
}
for(int i=2;i<n;i++){
if(ans[i]==ans[i-1]||ans[i]==ans[i+1])flag=1;
if(cmp(ans[i],ans[i-1])!=cmp(ans[i],ans[i+1]))flag=1;
}
if(flag){printf("NO\n");continue;}
printf("YES\n");
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
printf("\n");
}
return 0;
}