冬令营解题报告-奶牛浴场

《奶牛浴场》解题报告模型在平面的一个矩形中，有一些点组成集合P，要求一个面积最大的子矩形使得P中的点都在该子矩形之外（或者在子矩形的边框上算法0、L的线段上，Nxi(0<xi<L)求最长的一条子线段不包含P中的点（P中的点可以是线段端点Ax0 x5图Amaxofxi1xi0i=CBCBA 图（ 值从小到大排序。2）枚举确定上边界Top和下边界Bottom：将Top与Bottom之间的点按先前排序的顺序依次到线段上，扫描该方法的时间复杂度为O(N3)，显然无法在时间限制内出方法一之所以效率，其原因在于：枚举上下边界后，大致有2次的扫2次扫描是互相独立的，没有任何联系！如果能够弄清它们之间的充分利用以前的信息，在已知的基ACB例如图三所示：确定上下边界后，A和C被到线段上。扫描得“最宽的一带”为AC。ACB A 图在一维线段 了B点CBA在一维线段 了B点CBAB 图因此，所造成的变化是局部的。可以抓住这个关键性质，对原算法进行假设即将的是B点，那么要做以下工作在当前线段中找在B点之前且离BB点之后且离B先来解决：在当前线段中找在BB点最近的点。如图五所示，不妨将点按照x离散化，重新整理。x23x2347891234567图23 789xN个不同的标号。ACB后的标号为A1，C6ACB A 图在left与right之间（包含）的点共都total个。如图七所示：

图 total=0total=0total=1作就可以找到当前线段中在B点之前且离B点最近的点A了。类似的，B点也只需要logN次的操作。经过logN次的操作，得到了在B点之前的离B最近的点A以及在点之后离B最近的点C这样一来，寻找“最宽的一带”只要堆顶即可，时间复杂度 O(1)由此可以整理出解决本题的另法——方法二枚举确定上边界下边界Bottom从上往下移动，每移动一次，按已排好的顺序相应的点。用O(logN)的时间寻找和点，在用O(logN)的时间增删长度，最后用O(1)的时间得到当前“最宽的一带更新当前最优解。该方法的时间复杂度为O(N2logN)，比方法一有所提方法二利用到了每次扫描之间的联系，将静态的统计转变为动态的变化，利用线段树和堆为媒介，进行动态的更新操作并不断得到当前最优解。BCABCA 图BACB下边界往上移动一次后，造成的影响是删除了BBACB A 图例如图八中，Next(A)=B，Father(B)=A。要删除BNext(Father(B))=Next(B)Father(Next(B))Father(B)。这样的操作时间复杂度为O(1)B点对长度所造成的影响是：ABAC不存在了，新增了AC。由于AC一定不低于AB和AC，只要判断AC是否比当前“最宽的一带”如此，稍做变化后就得到了一种更快的算法——方法三将点按y枚举确定上边界初始时，所有Top与x轴之间的点，构造链表Next与Father。随Bottomx轴开始往上移动。按照已排好的顺序，在链表上删该方法的时间复杂度仅为O(N2)，完全可以在时限内出方法二与方法三大同小异，为什么有如此差别呢？原因在于：方法二中，下边界从上往下移动，需要点，并且得到的“最宽的一带”呈缩短趋势，所以要用堆来保存和。而方法