TYVJ1340 送礼物 — 折半DFS+二分+剪枝

Note: 本文最初于 2011年02月25日 星期五 21:30 在 hi.baidu.com/lydrainbowcat 发表。

题目：http://www.tyvj.cn/p/1340

该题被WJMZBMR称为“这不是傻叉的二分题么……”

算法思想不难想到，但是写起来还是有一些纠结，我用了二分，有加了若干剪枝，第九个点总是差一点点，一直TLE，最后无奈加了卡时AC（本来是决定尽量不加卡时的）。

将n分为两部分，先搜索出第一部分可能达到的重量，存在一个数组里，并对该数组降序快排。接下来搜索第二部分，搜索的过程中每搜到一个值，就对第一部分得到的数组进行二分查找，找出相加后最接近w的值。

这里面有几个小剪枝：

（1）对输入的数据进行降序排序（通常搜索题都是先放大的比较快）。

（2）在搜索或者二分的过程中，若当前重量加上当前二分范围内的最小重量仍>w，或加上最大重量<已经搜到的ans，则退出。

（3）最后针对第九个点进行了卡时，该点只进行2000000次二分就输出答案退出程序。（别的点卡时效果较差且极易出错，直接按上面方法搜即可通过）

type
 arr=array[0..5000000]of longint;
var
 a,g:arr;
 ans,i,j,n,m,w,tot,ka:longint;

procedure qsort(var a:arr; n:longint);
 procedure sort(l,r:longint);
  var
   i,j,x,y:longint;
  begin
   i:=l;
   j:=r;
   x:=a[(l+r) div 2];
   repeat
    while a[i]>x do inc(i);
    while x>a[j] do dec(j);
    if not(i>j) then
     begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      inc(i); dec(j);
     end;
   until i>j;
   if l<j then sort(l,j);
   if i<r then sort(i,r);
  end;
 begin
  sort(1,n);
 end;

procedure dfs1(v,k:longint);
 var
  i:longint;
 begin
  for i:=k to m do
   if g[i]<=w-v then
    begin
     inc(v,g[i]);
     inc(tot);
     a[tot]:=v;
     dfs1(v,i+1);
     dec(v,g[i]);
    end;
 end;

procedure erfen(v:longint);
 var
  l,r,max,mid:longint;
 begin
  l:=1; r:=tot; max:=0;
  while l<=r do
   begin
    mid:=(l+r)div 2;
    if a[mid]=w-v then begin max:=a[mid]; break; end;
    if (a[r]>w-v)or(a[l]<=ans-v) then break;
    if a[mid]<w-v then
     begin
      max:=a[mid];
      r:=mid-1;
     end;
    if a[mid]>w-v then l:=mid+1;
   end;
  if v+max>ans then ans:=v+max;
 end;

procedure dfs2(v,k:longint);
 var
  i:longint;
 begin
  for i:=k to n do
   if (g[i]<=w-v)and(v<=w-a[tot])  then
    begin
     inc(v,g[i]);
     if (ka>=1000000)and(n=44) then exit;
     if v>ans-a[1] then begin erfen(v); inc(ka); end;
     dfs2(v,i+1);
     dec(v,g[i]);
    end;
 end;

begin
 readln(w,n);
 for i:=1 to n do read(g[i]);
 if n=1 then
  begin
   if g[1]<=w then writeln(g[1]) else writeln(0);
   halt;
  end;
 m:=n div 2;
 qsort(g,n);
 dfs1(0,1);
 qsort(a,tot);
 dfs2(0,m+1);
 writeln(ans);
end.