POJ 1818(贪心）

让每个人每局都与可战胜的人中最强的打,看有无可行解……

Program p1818;
var
   n,x,k,i,j,mid:longint;
   q:array[1..5100] of longint;
   f:array[1..5100] of longint;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function is_ac(person:longint):boolean;
var
   i,j,l,h,t:longint;
   size:longint;
begin
   fillchar(f,sizeof(f),0);
   fillchar(q,sizeof(q),0);
   q[1]:=person;
   size:=1;
   f[person]:=1;
   h:=1;t:=1;
   for l:=2 to x+1 do
   begin
      for i:=h to t do
      begin
         for j:=max(1,q[i]-k) to n do
         begin
            if f[j]=0 then
            begin
               inc(size);
               q[size]:=j;
               f[j]:=l;
               break;
            end;
         end;
      end;

      t:=size;

   end;

   if (size<n) then exit(false)
   else exit(true);


end;
begin
   read(n,k);
   x:=0;
   i:=1;
   while (i<n) do
   begin
      inc(x);
      i:=i shl 1;
   end;

   i:=1;j:=n;
   if is_ac(j) then i:=j;
   while (j-i>1) do
   begin
      mid:=(i+j) shr 1;
      if is_ac(mid) then i:=mid else j:=mid;
   end;
   writeln(i);
end.