aggr.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 54 行

{
PROB:aggr
LANG:PASCAL
}

program aggr;
const
  maxn=100000;
var
  x:array[1..maxn]of longint;
  n,c,i,l,r,m,last,count:longint;
procedure qsort(s,t:longint);
  var
    p,i,j,tx:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tx:=x[p];x[p]:=x[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (x[j]>=tx) do dec(j);
      if i=j then break;x[i]:=x[j];inc(i);
      while (i<j) and (x[i]<=tx) do inc(i);
      if i=j then break;x[j]:=x[i];dec(j);
    until i=j;
    x[i]:=tx;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
begin
  assign(input,'aggr.in');reset(input);
  assign(output,'aggr.out');rewrite(output);

  read(n,c);
  for i:=1 to n do
    read(x[i]);
  qsort(1,n);

  l:=0;r:=x[n]-x[1];
  repeat
    m:=(l+r+1) shr 1;
    last:=1;count:=1;
    for i:=2 to n do
      if x[i]-x[last]>=m then begin
        last:=i;inc(count);
        if count>=c then break;
      end;
    if count<c then r:=m-1 else l:=m;
  until l=r;

  writeln(l);
  close(input);close(output);
end.