简易贪心+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.