集训队作业奶牛浴场解题报告

1、奶牛浴场解题题目简述在一个长方形有一些点。在这个长方形内求一个边界与它平行且面积最大的长方形，同时这个长方形的（不包括边界）没有给出的点。算法分析要解决这道题，搜索是必不可少的。怎么搜呢？如果分别枚举长方形的四条边，再判断该长方形是否有点，那么这种方法的时间复杂度将高达O（nL2W2）。这个时间复杂度是无法接受的。如果，对坐标进行离散化，那么时间复杂度将降为 O（n5）。如果根据点的坐标对它们排序，再枚举正方形的三条边，那么这个算法的时间复杂度可以降为 O（n4）。如果只枚举正方形的两条边（可以是对边，也可以是相邻边），那么算法的时间复杂度可以降为O（n3）那么，这道题目究竟该怎么搜呢？吧。还

2、是先对要求的长方形作一番分析这个长方形必须满足以下两大条件：面积最大（不包括边界）不含点，且在大长方形的于是，可以得到下述结论：固定这个长方形的任意三条边，那么剩下的一条边一定不能向外推进。（否则就与其面积最大！）所以，这个长方形的每一条边都满足如下性质：它要么在大长方形的边界上，要么有一个点在这条边的（不包括端点）。这条性质给的解题带来了很大的帮助只要枚举所有满足上述性质的长方形，求出其中面积的最大值即可。作为预处理，先以x 轴坐标的值为关键字对所有的点排序。着重考虑长方形的左边界。它要么在大长方形的左边界上，要么经过大长方形的一个点。于是，分两种情况考虑：左边界经过一个点把长方形的下边界定

3、为 0，上边界定为W。从点A 向右依次枚举每一个点，并把长方形的右边界不断地右移。适当修改上下边界的值，使得长方形的没有点。当遇到某一个点P 在当前的上下边界的范围内，则分两种情况：图 1若 P 即为长方形的右边界。那么计算当前长方形的面积，并与最大值进行比较。若长方形的右边界在 P 的右方，那么其上下边界的值就必须修改。当 PBAC在A 的上方时，把长方形的上边界改为 P 的 y 坐标值（如图 1 中点 B）；当 P 在 A 的下方时，把长方形的下边界改为 P 的 y 坐标值（如图 1 中点 C）。最后以x=L 为右边界，计算当前长方形的面积，并与最大值进行比较。左边界在大长方形的左边界上枚

4、举长方形的下边界。固定长方形的下边界，初始时把长方形的上边界定为W。从左向右依次枚举每一个点，并把长方形的右边界不断地右移。适当修改上边界的值，使得长方形的没有点。当遇到某一个点 P 在当前的上下边界的范围内，则分两种情况：若 P 即为长方形的右边界。那么计算当前长方形的面积，并与最大值进行比较。若长方形的右边界在 P 的右方，那么其上边界的值就必须修改。把长方形的上界改为P 的 y 坐标值。最后以 x=L 为右边界，计算当前长方形的面积，并与最大值进行比较。x图 2对 n 个点排序的时间复杂度为 O(nlgn)。情形 的时间复杂度为 O(n)且要执行 n 次。情形 的时间复杂度为 O(n2)

5、且只要执行 1 次。所以该算法总的时间复杂度为O(n2)，空间复杂度为O(n)。小结这虽然是一道，但仍不失为一道非常好的题目。它的解法多种多样，从O(nL2W2)到O(n2)，差距相当之大。而只有 O(n2)的算法才能适应本题的数据规模。这道题目给我上了生动的一课做搜索题决不手拈来，要充分考虑时间复杂度，三思而后行。一个好的解法离不开对题目的透彻地分析，只有抓住了其本质才能出奇制胜。所谓“一山更比一山高”，题目的解法也是如此。切勿盲目地满足于自己的解法。本题解法的从O(nL2W2)到O(n5)，又降到 O(n4)，再降到O(n3)，最后降为O(n2)，正说明了这一点。在解决本题的过程中，真切地

6、体验了一回“山重水复疑无路，又一村”。附录一：源程序varx,y,z:array0.5000 of long;x,y 点的坐标;z 纵坐标值离散化l,w 大长方形的长和宽i,j,l,w,n:long;P5P1P4P3下边界P2bx,by,k,y1,y2,max:long;max 长方形面积的最大值procedure qsort1(p,q: var i:eger;begini:=random(q-p+1)+p; bx:=xi;by:=yi; xi:=xp;yi:=yp; i:=p;j:=q;while ij do begineger);根据点的x 坐标值快速排序while (i=bx) do d

7、ec(j); xi:=xj;yi:=yj;while (ij)and(xi=bx) xj:=xi;yj:=yiend; xi:=bx;yi:=by;if pi+1 then qsort1(i+1,q)end;nc(i);procedure qsort2(p,q: var i:eger;begini:=random(q-p+1)+p; k:=zi;zi:=zp; i:=p;j:=q;while ij do begineger);对数组z 快速排序while (i=k) do dec(j); zi:=zj;while (ij)and(zi=k) zj:=ziend; zi:=k;if pi+1 t

8、hen qsort2(i+1,q)end;nc(i);procedure check(s:long); beginif smax then max:=s end;最大面积值beginassign(input,happy.in); reset(input); readln(l,w);readln(n); j:=0;for i:=1 to n do begin inc(j); readln(xj,yj);读入数据if (xj=0)or(xj=l)or(yj=0)or(yj=w) then dec(j)若该点在大长方形的边界上，则删去该点end; n:=j;qsort1(1,n); z:=y; qs

9、ort2(1,n);z0:=0;对读入的点排序纵坐标值离散化if n=0 then max:=l*w else max:=0;for i:=0 to n doif (i=0)or(zizi-1) then begin k:=w;for j:=1 to n do处理无点的情况最大面积值初始化情形 枚举下边界暂定上边界从左向右依次枚举每一个点if (yjzi)and(yjk) then begin若该点在当前上下边界范围内check(k-zi)*xj); k:=yjend;check(k-zi)*l) end;for i:=1 to n do begin y1:=0;y2:=w; j:=i+1;w

10、hile (j=n)and(xj=xi) while jy1)and(yjy2) then begin 若P 在当前的上下边界的范围内check(y2-y1)*(xj-xi); if yj=yithen y1:=yj计算以 P 为右边界的长方形的面积若P 在A 的下方，修改下边界else y2:=yj end;inc(j) end;check(y2-y1)*(l-xi) end;若P 在A 的上方，修改上边界计算以x=L 为右边界时的面积assign(output,happy.out); rewrite(output);wrin(max); close(output)end.输出面积的最大值附

11、录二：题目描述奶牛浴场happy.exe【问题描述】由于 John 建造了牛场围栏，激起了奶牛的，奶牛的产奶量急剧减少。为了讨好奶牛，John 决定在牛场中建造一个大型浴场。但是 John 的奶牛有一个奇怪的，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John 希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于 Clevow 了。你还能帮助 Clevow 吗？John 的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。Clevow 当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。【输入文件】输入文件的第一行包含两个整数 L 和 W，分别表示牛场的长和宽。文件