简易贪心+heap

注意要用链表

 type link=^node;
     node=record
       loc:longint;
       next:link;
     end;
     point=record
       loc,num:longint;
     end;
var w,b:array[..] of link;
    heap:array[..] of point;
    n,k,s,x,i,j,y,t,ans:longint;
    p,q:link; function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end; procedure swap(var a,b:point);
  var c:point;
  begin
    c:=a;
    a:=b;
    b:=c;
  end; procedure up(i:longint);
  var j:longint;
  begin
    j:=i shr ;
    while j> do
    begin
      if heap[i].loc<heap[j].loc then
      begin
        swap(heap[i],heap[j]);
        i:=j;
        j:=i shr ;
      end
      else break;
    end;
  end; procedure sift(i:longint);
  var j:longint;
  begin
    j:=i shl ;
    while j<=k do
    begin
      if (j+<=k) and (heap[j].loc>heap[j+].loc) then inc(j);
      if heap[i].loc>heap[j].loc then
      begin
        swap(heap[i],heap[j]);
        i:=j;
        j:=i shl ;
      end
      else break;
    end;
  end; begin
  readln(n,k);
  for i:= to k do
  begin
    read(s);
    w[i]:=nil;
    for j:= to s do
    begin
      read(x);
      new(p);
      p^.next:=nil;
      p^.loc:=x;
      if w[i]=nil then
      begin
        w[i]:=p;
        q:=p;
      end
      else begin
        q^.next:=p;
        q:=p;
      end;
    end;
    b[i]:=w[i];
    readln;
  end;
  y:=;
  for i:= to k do
  begin
    t:=t+;
    heap[t].loc:=b[i]^.loc;
    heap[t].num:=i;
    up(t);
    if heap[t].loc>y then y:=heap[t].loc;
    b[i]:=b[i]^.next;
  end;
  ans:=y-heap[].loc;
  while true do
  begin
    x:=heap[].num;
    if b[x]=nil then break
    else begin
      heap[].loc:=b[x]^.loc;
      if y<b[x]^.loc then y:=b[x]^.loc;
      b[x]:=b[x]^.next;
      sift();
      ans:=min(ans,y-heap[].loc);
    end;
  end;
  writeln(ans);
end.
05-11 09:37