POJ 2456(二分哲学）

哲学）"/>

POJ 2456(二分哲学）

法一：只循环60遍，用ans记录答案(见标程）

法二：进行特判，若l+1==r 则 m=(l+r+1) shl 1 否则 m=(l+r) shl 1

Program P2456;
constmaxd=1000000000;maxn=100000;
varn,c,i,j,k:longint;a:array[1..maxn] of longint;
procedure sort(l,r:longint);
varm,i,k,head,tot,ans:longint;
beginfor k:=1 to 60 dobeginm:=(l+r) shr 1;head:=1;tot:=0;for i:=2 to n dobeginif a[i]-a[head]>=m thenbegininc(tot);head:=i;end;end;if tot>=c-1 then begin ans:=m; l:=m+1 end else r:=m-1;end;writeln(ans);end;
procedure qsort(l,r:longint);
vari,j,m,p:longint;
begini:=l;j:=r;m:=a[(l+r) shr 1];repeatwhile a[i]<m do inc(i);while a[j]>m do dec(j);if i<=j thenbeginp:=a[i];a[i]:=a[j];a[j]:=p;inc(i);dec(j);end;until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);
end;
beginread(n,c);for i:=1 to n do read(a[i]);qsort(1,n);sort(1,maxd);end.