集訓(xùn)隊作業(yè)魔術(shù)眼鏡盒

1、魔術(shù)眼鏡盒2005 組隊賽問題分析：顯然，要使得放置的紙片盡量多，必然要將最小的幾張卡通紙片和最小的幾張公式紙片放入。并且，在所有被放入眼鏡盒的紙片中，“最大的卡通紙片一定對應(yīng)最大的公式紙片，次大的卡通紙片一定對應(yīng)次大的公式紙片”，依次類推。（這個證明在算法分析后面）可以對卡通紙片和公式紙片分別從小到大排序，成為兩個有序的線性表。然后移動線性表的相對位置（用枚舉兩個表頭的元素的位置差來實現(xiàn)），并通過事件列表來降低移動的復(fù)雜度。時間復(fù)雜度是排序和創(chuàng)建事件列表的復(fù)雜度 O(nlogn)。證：反證法。假設(shè)公式紙片 a1,a2(a1a2)，卡通紙片 b1,b2(b1b2)，a1 和 b2 對應(yīng)，a2

2、和 b1 對應(yīng)。下證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 為當(dāng)前眼鏡盒的長度，h 為當(dāng)前選取公式卡片的數(shù)量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、 是當(dāng)前眼鏡盒的寬度while (h0) or (h+d0) do/當(dāng)選取的公式紙片和卡通紙片的數(shù)量都不為 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 為當(dāng)前的紙片總數(shù)if h+d0 then temc:=temc+(h+d);if temc0thentems:=s*welsetems:=0;/tems 為當(dāng)前的眼睛盒面積if (temcbestc) or (temc=bestc) and (temsbests) then begin/找到了更優(yōu)的解bestc:=temc; bests:=temsendend;/輸