题目背景

上次老师挑出来的(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 ;
}
05-08 08:35