"离散化：程序设计中的常用技巧"

离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。对于“什么是离散化”，有各种不同的说法，比如“排序后处理”、“对坐标的近似处理”等等。事实上，所有这些说法都是正确的。离散化需要一些例子和不少的讲解才能完全解释清楚。 举例来说，《算法艺术与信息学竞赛》中的计算几何部分，黄亮举了一个经典的例子，就是很适合用来介绍离散化思想。这个问题是UVA10173，题目意思很简单，给定平面上n个点的坐标，求能够覆盖所有这些点的最小矩形面积。这个问题之所以难，是因为这个矩形可以倾斜放置，边不必平行于坐标轴。处理倾斜放置是非常困难的，因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α，那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点。也就是说，四条边的斜率已经都知道了的话，只需要让这些边从外面不断逼近这个点集直到碰到了某个点。这个具体应该怎么实现就不必过于深究，只需要理解这个思想。 另一个例子是校门外的树问题。在这个问题中，我们需要在一条长度为L的马路上移走一些树，这些树所在的范围可以用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。我们的任务是计算将这些树都移走后，马路上还有多少棵树。由于问题规模不大，可以直接模拟暴力求解。 这些例子展示了离散化的思想和应用。离散化不仅可以应用于计算几何问题，还可以用于很多其他类型的问题，例如区间覆盖等。通过将连续的值离散化为有限的取值，我们可以很大程度上简化原问题的复杂度，从而更高效地解决问题。 综上所述，离散化是一个非常有用的程序设计技巧，它能够有效降低时间复杂度，适用于各种类型的问题。虽然对于“什么是离散化”有各种不同的说法，但其基本思想是一致的：在众多可能的情况中“只考虑我需要用的值”。通过例子的讲解，我们可以更好地理解离散化的思想和应用，从而更好地运用到实际问题中，提高程序的效率和性能。