【题目描述】 有 N 个人顺时针围在一圆桌上开会，他们对身高很敏感。 因此决定想使得任意相邻的两人的身高差距最大值最小。 如果答案不唯一，输出字典序最小的排列，指的是身高的排列。N<=5500 【输入格式】 第一行一个整数N 第二行有N个整数, 第i个整数表示第i个人的身高hi, 1<=hi<=1000。 按顺指针给出N个人的身高 【输出格式】 第一行一个整数表示相邻的两人的身高差距最大值最小值 第二行N个整数表示字典序最小的最优排列 【样例输入】 5 1 3 4 5 7 【样例输出】 3 1 3 5 7 4 【分析】 看到“最大值最小”就会想到二分。对于此题可以二分最大的身高差，再用贪心验证一下即可。 那么如何贪心呢？首先可以证明，把A2放在A1左边，A3放在A1右边，A4放在A2左边，A5放在A3右边等等，这种方法是不可行的。 我们可以先把A1放在第一位，然后每次在后面尽可能的放上一个大的Ai，在前面尽可能的放上一个小的Aj（但是Ai和Aj都必须满足身高差），放完的时候判断身高差是否满足要求即可。
var n,i,ans,max,min,x:longint; a,b,c:array[0..100000] of longint; p:array[0..100000] of boolean; pd:boolean; procedure check; var head,tail,ct,ch,i,ii,q:longint; pt:boolean; begin fillchar(p,sizeof(p),true); fillchar(b,sizeof(b),0); pd:=false; b[1]:=a[1]; p[1]:=false; head:=2; tail:=n; ct:=1; ch:=1; pt:=true; while pt do begin if head>tail then begin if abs(b[head]-b[tail])<=x then pd:=true; exit; end; if head=tail then begin for i:=1 to n do if p[i] then begin ii:=i;break; end; if (abs(a[ii]-b[head-1])<=x)and(abs(a[ii]-b[tail+1])<=x) then begin b[head]:=a[ii]; pd:=true; exit; end; end; if p[n] then begin q:=1; for i:=n downto 1 do if p[i] then if abs(a[i]-b[ct])<=x then begin q:=i;break; end; if q=1 then exit; p[q]:=false; b[tail]:=a[q]; ct:=tail; dec(tail); end; q:=1; for i:=1 to n do if p[i] then if abs(a[i]-b[ch])<=x then begin q:=i;break; end; if q=1 then exit; p[q]:=false; b[head]:=a[q]; ch:=head; inc(head); end; end; procedure search(l,r:longint); begin x:=(l+r) div 2; check; if pd then begin ans:=x; c:=b; if (l<>r)and(x-1>=l) then search(l,x-1) end else if (l<>r)and(r>=x+1) then search(x+1,r); end; procedure qsort(l,r:longint); var i,j,x,y:longint; begin i:=l; j:=r; x:=a[(i+j) div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin y:=a[i];a[i]:=a[j];a[j]:=y; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin read(n); fillchar(a,sizeof(a),0); min:=maxlongint; max:=0; for i:=1 to n do begin read(a[i]); if a[i]<min then min:=a[i]; if a[i]>max then max:=a[i]; end; qsort(1,n); fillchar(c,sizeof(c),0); search(1,max-min); ans:=abs(c[n]-c[1]); for i:=1 to n-1 do if ans<abs(c[i+1]-c[i]) then ans:=abs(c[i+1]-c[i]); writeln(ans); for i:=1 to n do write(c[i],' '); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533493.html
