离散化

发表于 | 分类于 | | 热度: ℃

定义

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。也就是说，我们不关心数据的真实大小，只关心数据的 相对 大小。比如我们要把 $1e5$ 个范围是 $1e9$ 的数进行并查集。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1000005;
int n, m, a[N], t[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        t[i] = a[i];
    }
    sort(t + 1, t + n + 1);
    m = unique(t + 1, t + n + 1) - t - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(t + 1, t + m + 1, a[i]) - t;
    return 0;
}

其中 $unique$ 返回的是去重后的 尾地址 ，需要减去首地址才能使用。$lower$_$bound$ 返回的是左闭右开区间 $[first,last)$ 中第一个大于等于 $val$ 的元素地址（也就是说 $last$ 是越界的）