对于离散化方法的研究

· · 个人记录

对于离散化方法的研究

引言

在做题的过程中，我们会遇到这样一类题目： 读入一个长度为 n 的序列 a，其中 a_i 值域非常大（限制常常是 a_i \in \{x\in\mathbf Z|-10^9 \le x \le 10^9\}），但 n 不大（一般在 10^5 级别），然后处理输出。

这一类题目主算法的时间复杂度往往是 O(n) 到 O(n \log_2 n) 的，但有时算法要求要在 a_i 的值域上遍历，而巨大的值域会使程序的时空复杂度变得不可接受。

这时候，我们就需要通过离散化降低程序时空复杂度，从而解决问题。

基本思想

离散化是程序设计中一个常用的技巧，其基本思想是在众多元素中，只考虑关键的部分元素。

离散化是在保留元素的某些特征或顺序的前提下，把极大甚至无限的空间中有限的个体映射到有限且较小的空间中去，以此提高算法的时空效率。被离散化的元素可以是大整数、浮点数、字符串等等。

离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。

实现

数的离散化

对于数而言，可以将数排序，排序后的编号即为其离散化后的值。

配合上 STL，这种方法实现非常简单，代码如下：

//included algorithm
//以下代码对 raw 数组离散化
sort(raw+1,raw+n+1); //排序
//len：非重复元素的数目
len=unique(raw+1,raw+n+1)-raw-1; //去重
int rank(int value){ //该函数返回 value 离散化后对应的值
    lower_bound(raw+1,raw+len+1,value)-raw;
}

如果觉得这种方式不太自然，也可以使用 map 或结构体记录数离散化后的值。

其它数据的离散化

多数情况下，对于其它数据，离散化保留的是原数据与整数之间的一一对应关系。

可以使用 map 进行其它数据的离散化。

//included map
//将数据从 type 类型映射到 int
map<type,int> mp;
//rank：离散化后的值（也可以直接是数据）
mp.insert(make_pair(type a,int rank));
//离散化后的值
mp[a]

例题

  1. Luogu P1496 火烧赤壁

  2. Luogu P3740 [HAOI2014] 贴海报

  3. CF2A Winner

参考资料

  1. 离散化 - OI Wiki
  2. 离散化 - 百度百科

本文的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供。