离散化是程序设计中一个非常常用的技巧,它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明,如何运用离散化改进一个低效的,甚至根本不可能实现的算法。
这里的倾斜放置很不好处理,因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α,那么答案就很简单了:矩形面积最小时四条边一定都挨着某个点。也就是说,四条边的斜率已经都知道了的话,只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现,只需要理解这可以通过某种方法计算出来,毕竟我们的重点在下面的过程。
“离散化”了。虽然这个算法仍然有优化的余地,但此时我们已经达到了本文开头所说的目的。
永远是离散化的经典问题。大意是给定平面上的n个矩形(坐标为整数,矩形与矩形之间可能有重叠的部分),求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”(把矩形所在的位置填上True)。可惜这个想法在这里有些问题,因为这个题目中坐标范围相当大(坐标范围为-10^8到10^8之间的整数)。但我们发现,矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值,
100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说,实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面,省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数,于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标(或纵坐标)进行一次排序并映射为1到2n的整数,同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。
Limit
Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序,然后同样用时间段的开始点和结束点来计算每个时刻的游戏数,只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样,一个1..n的数组就足够了。
2007.04.05补充:
VOJ1056那个例子看来还是有人不明白。
我发一张示意图,注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的
出自matrix67.com,谢谢大牛的讲解。