题目背景
上次老师挑出来的（N-K）位同学很不高兴，于是他们准备自己组建合唱队形。他们请了kkk来帮忙。
题目描述
他们安排了一个动作——手拉着手唱一首歌（就是他们围成一个圈）。如果有两个相邻的同学的身高差非常大（比如姚明和一个1.5米高的人站在一起）的话，评委会感觉非常不爽。于是kkk需要帮助他们求出一种排队方案，使他们身高差距最大值最小，并输出这个最小值和这个方案。
输入输出格式
输入格式：
第一行一个整数N表示有N个人（排成一个圈）
第二行N个整数表示每个人的身高
输出格式：
第一行一个整数表示最小的身高差距最大值
第二行N个整数表示这个最优方案，如果多解输出字典序最小
输入输出样例
输入样例#1：
6
1 2 3 4 5 6
输出样例#1：
2
1,2,4,6,5,3
说明
1<=N<=6000
1<=身高<=1000
思路：
先把身高排序
然后我们就用一个很神奇的环来得出答案
把1作为环的一个点
2~n的元素如果第i个元素的i%2==1放到右边
否则放到左边成为一个环
然后判断哪两个之间的身高差最大
这样就能得出来第一问的答案
现在就是要解决字典序的问题了
把排序后的身高进行编环
还是把最矮的放到第一位
然后如果第i+1个元素-第i个元素>ans
就把第i个元素放到第最左端
否则放到最右端
完成后左右两端链接成为环
从最矮的往后输出就是答案
来，上代码：
#include<cmath>
#include<cstdio>
#include<algorithm> using namespace std; struct node {
int now,dis;
};
struct node ai[],loop[]; int n,maxn,minn,num=,ans=; bool if_in[]; bool cmp(struct node SOME_1,struct node SOME_2){return SOME_1.dis<SOME_2.dis;} void sort_1()
{
int now_1=,now_2=n,now_3=,cur_1=ai[].dis;
loop[]=ai[now_3++];
while(now_3<=n)
{
if(now_3==n) loop[++now_1]=ai[now_3++];
else
{
if(ai[now_3+].dis-cur_1<=ans)
{
loop[++now_1]=ai[now_3++];
}
else
{
cur_1=ai[now_3].dis;
loop[now_2--]=ai[now_3++];
}
}
}
int v=,cnm[],now_4=;
for(int i=v;i<=n;i++) cnm[++now_4]=loop[i].dis;
for(int i=;i<v;i++) cnm[++now_4]=loop[i].dis;
for(int i=;i<n;i++) printf("%d,",cnm[i]);
printf("%d\n",cnm[n]);
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
ai[i].now=i;
scanf("%d",&ai[i].dis);
}
sort(ai+,ai+n+,cmp);
loop[++num]=ai[];
for(int i=;i<=n;i++) if(i%==) loop[++num]=ai[i];
for(int i=n;i>=;i--) if(i%==) loop[++num]=ai[i];
for(int i=;i<n;i++) ans=max(ans,abs(loop[i].dis-loop[i+].dis));
ans=max(ans,abs(loop[n].dis-loop[].dis));
printf("%d\n",ans);
sort_1();
return ;
}