【算法】离散化

其实离散化就是排序的一个应用,对于有多种关系都可以直接模一个数来达到离散化的目的233,有冲突几率看脸。

通俗的讲:离散化就是把无穷大的集合中若干个元素映射到有限集合以便于统计的方法。

例如,在某些情况下,问题的范围虽然定义在整数集$Z$中,但只涉及其中$m$个数,并且与数值的绝对大小无关。此时,我们可以把$Z$中的这$m$个数与$1$~$m$建立映射关系。

具体来说,假设问题涉及$int$范围内的$n$个整数$a[1]$~$a[n]$,这$n$个整数可能有重复,去重以后共有$m$个整数。我们要把$a[i]$用一个$1$~$m$的整数代替,得到$b[]$,并且保持大小顺序不变。

做到这一点很简单,对$a[]$排序后去重即可,然后查询$i(i\leq i\leq m)$代表的数值,只需要返回$b[i]$;若要查询$a[j](1\leq j\leq n)$被哪个$1$~$m$的整数替代,只需在$b[]$中二分查找$a[j]$的位置即可。

void discrete(){
	sort(a + 1,a + n + 1);
	unique(a + 1,a + n + 1);
}

void query(int x){
	return lower_bound(b + 1,b + m + 1,x) - b;
}