集训队作业魔术眼镜盒

1、魔术眼镜盒2005 组队赛问题分析：显然，要使得放置的纸片尽量多，必然要将最小的几张卡通纸片和最小的几张公式纸片放入。并且，在所有被放入眼镜盒的纸片中，“最大的卡通纸片一定对应最大的公式纸片，次大的卡通纸片一定对应次大的公式纸片”，依次类推。（这个证明在算法分析后面）可以对卡通纸片和公式纸片分别从小到大排序，成为两个有序的线性表。然后移动线性表的相对位置（用枚举两个表头的元素的位置差来实现），并通过事件列表来降低移动的复杂度。时间复杂度是排序和创建事件列表的复杂度 O(nlogn)。证：反证法。假设公式纸片 a1,a2(a1a2)，卡通纸片 b1,b2(b1b2)，a1 和 b2 对应，a2

2、和 b1 对应。下证begini:=l;j:=r;x:=pp(l+r) div 2; repeatwhile ppixnc(i);while xppj do dec(j); if ij;if lj then sort(l,j); if i1 dobegin/ 符号是取地址运算，这里的用途是避免写两遍排序过程/从小到大排序/清空事件列表/寻找最小的 j，满足xixi then max:=mid else min:=mid end;cxi:=max-i;/将这一事件加入列表中 new(p);with p do beginr:=i;v:=-xi; next:=headcxiend;headcxi:=

3、p end;for i:=1 to n do beginmin:=0;max:=m+1;/二分寻找最大的 j，满足 xj1 dobeginmid:=(max) div 2;if xmidyi then min:=mid else max:=mid end;cyi:=i-min;/将这一事件加入列表中 new(p);with p do beginr:=i;v:=yi; next:=headcyiend; headcyi:=pend;/计算最多能放多少卡通纸片s:=0;h:=m;for i:=1 to m do/s 为当前眼镜盒的长度，h 为当前选取公式卡片的数量if (s+xi)*xi0then

4、 bests:=s*xh else bests:=0;/bestc/面积 for d:=-m+1 to n do beginp:=headd;whilepnildo beginwith p do if v0then if r=h+dthen s:=s+v最多能放置多少纸片，bests放 bestc 张纸片时所需要的最小/枚举 d，即两个表头的元素的位置差/headd为此时需要处理的事件列表的表头else else if r=hthen s:=s+v else;p:=p.next; end;if (h+d=n) and (cyh+dn then dec(h);w:=0;/判断 h 是否溢出/ w

5、 是当前眼镜盒的宽度while (h0) or (h+d0) do/当选取的公式纸片和卡通纸片的数量都不为 0 时beginif (h0) and (xhw) then w:=xh;if (h+d0) and (yh+dw) then w:=yh+d; if s*w0then temc:=temc+h;/temc 为当前的纸片总数if h+d0 then temc:=temc+(h+d);if temc0thentems:=s*welsetems:=0;/tems 为当前的眼睛盒面积if (temcbestc) or (temc=bestc) and (temsbests) then begin/找到了更优的解bestc:=temc; bests:=temsendend;/输