解题报告SPOJZebraCrossingCustom.docVIP

解题报告 SPOJ Zebra Crossing Custom 【题目描述】 一条宽度为W的马路，N个人站在马路的某一边，0时刻每个人都以自己的速率和方向开始过马路（运动的过程中，速率和方向不变）。你可以任意选一个位置作为起始点，一个速率（速率有最大值限制）和方向，从0时刻混在那N个人中过马路（过马路的过程中的速率和方向不变），要求途中碰到的人尽可能的多（碰到的意思是，在某一时刻两个人的X,Y坐标相等，碰撞不会对方向速率造成任何影响）。 给定N个人的初始位置和他们过马路的速率方向，求出最多能碰到多少人。 【分析】 首先，把所有人的速度按X，Y方向分解，容易知道，碰到的人的Y方向速率肯定相等。所以，只要考虑Y方向速率相同的一群人。 好的，现在所有人的Y方向速率相同了。只要考虑X方向了。 把每个人的运动轨迹画出来，自己的运动轨迹也画出来，那么在Y速率相同的前提下，两人相撞等价于运动轨迹相撞。 假设，现在从SX出发，X方向速率是VX，Y方向速率是VY（VY等于这些人的），终点是TX=SX+VX*W/VY，能够碰到最多的人。 那么，可以把SX左移，直到SX碰到某个人的起始点，或者TX碰到某个人的终点。由于碰到终点的情况可以把马路翻过来考虑，所以只考虑碰到起始点的情况。 现在SX卡在了某个人的起始点上了，那么可以把X方向速率伸缩，直到TX碰到某个人的终止点，或者到达速率的最大值。 就是说，任何一个最优解，肯定可以通过平移＋伸缩，使得起点在某个人的起点，终点在某个人的终点，或者是起点在某个人的起点，用最大速率向两边走。 先考虑最大速率的情况，枚举方向（左、右），然后，对于每个人，都可以算出一个区间，就是起点在这个区间中就能够与这个人相交。 将所有的区间算出来，重合部分最多的地方，放置起点，就能跟最多的人相交。这一种情况可以在O(NLogN)的时间做出来。 对于前一种情况，如果枚举上下的卡点，然后再判断，复杂度是O(N3)。下面给出一种O(NLogN)的方法。 枚举下面那个卡点，假设是I。 那么把I左边的人染红，把I右边的人染绿，如下图。 这个时候，上面的卡点假如是J（I-J不能超过最大速率能到的距离）的话，这种情况能碰到的人数就是J左边绿点的个数加上J右边红点的个数（包括J）。 所以只要能很快的求出上面的卡点J，使得J左边的绿点和右边的红点的数目最大。 把上面的终点按坐标序用1颗线段树维护。每个线段树节点[x,y]，设有best域，表示上卡点设在[x,y]区间中，最优值是best。 这样枚举了I以后，算出以最大速率的时候，能够到达的最左边的上卡点L和最右边的上卡点R，在线段树中查找[L,R]区间中的best最大值，就是下卡点为I的最大值。 对于任意中间节点的best，很容易根据它的两个儿子得出： Root.best=Max{Lchild.Best，Rchild.Best} 对于叶子节点，Leaf.Best=Gcount(1,X)+Rcount(Y,N) 其中Gcount(x,y)和Rcount(x,y)分别表示区间(x,y)中有多少个绿/红点。 Gcount,Rcount可以再用一颗线段树实现。 现在将I向右移动，这将使得1个绿色的线段变成红色，而这个改变只会在线段树中影响O(LogN)个节点，把这O(LogN)个节点更新一下，就能立刻算出当前的最优值。 而对于Gcount和Rcount，也能够在O(LogN)的时间内更新。 所以，只需要把I从最左边的点逐个向右滑动，每次更新最优值，就可以了。 整体的时间复杂度是O(NLogN)。 【附原题】 SPOJ Problem Set 231. The Zebra Crossing Problem code: ZEBRA Have you ever wondered why people collide with each other at pedestrian crossings? The reasons are probably difficult to analyse from a scientific point of view, but we can hazard a guess. A part of the problem seems to be that the statistical pedestrian, when faced with a red light, will either cross at once (this category of pedestrians doesnt really interest us, since they tend to collide with cars rather th