关于离散化的一点总结和心得

· · 个人记录

离散化

一、离散化的特点

离散化，就是把一些很离散的点给重新分配

二、使用离散化的经典特征

当数据的范围非常大或者其中含有负数，但数据本身的个数并不是很多时，如果每个数据元素的具体值并不重要，重要的是他们之间的大小关系的话，我们可以先对这些数据进行离散化。比如：102131511，123，9813186，-611，55。其中有非常大的数以及负数，会给许多算法的实现带来困扰，我们可以把这个序列离散化，使它变成这样：5，3，4，1，2。相当于原本数据范围仅限制定义类型而非数组大小等

不能忽视高精度，因为离散化之前，需要存储所有数据

三、离散化的实现

1、对原序列进行排序，使其按升序排列； 2、去掉序列中重复的元素； 3、此时序列中各位置的值和位置的序号就是离散化的映射方式。

还是上面那个例子：102131511，123，9813186，-611，55，55； 先进行排序：-611，55，55，123，9813186，102131511； 去重：-611，55，123，9813186，102131511； 此时，-611映射1，55映射2，123映射3，9813186映射4，102131511映射5，完成离散化。

int n, a[maxn], t[maxn];
for(int i = 1;i <= n;i++)
{
    scanf("%d", &a[i]);
    t[i] = a[i];//t是一个临时数组，用来得到离散化的映射关系
}
sort(t + 1, t + n + 1);//排序
int m = unique(t + 1, t + 1 + n) - t - 1;//去重，并获得去重后的长度m
for(int i = 1;i <= n;i++)
{
    a[i] = lower_bound(t + 1, t + 1 + m, a[i]) - t;//通过二分查找，快速地把元素和映射对应起来
}

四、和离散化搭配的知识点

说实话，离散化搭配的完全不是知识点，而是关于输入数据对解题的影响，所以单纯的找出和离散化配合比较多的类似于线段树，主席树等没什么用处，更多的还是参照第二点--使用离散化的经典特征比较合适。

五、离散化的经典套路

这个也没有多么好说的，离散化更像是一块磨刀石，刀法什么的和磨刀石是没有关系的。