离散化:将无限空间中的有限个体映射到有限的空间中。
比如说我有一个无尽的坐标轴,上面有 10^4 个点,每个点的坐标值可以很大很大接近无限。如果我想知道比其中一个点小的点有多少个,暴力比较每个点的坐标值则会因为数据过大而 Boom。而我们通过点与点相对关系,将点的值进行重新赋值,则可以大大减小算法的复杂度。
比如,我现在的数轴上只有6个点, 他们的坐标分别为 0、610、10^5+2、99、5、10^9+45,如果我只是按照他们原有的值进行比较,最大要比较到 10^9+45。而如果我们用他们的相对大小来进行比较,即转换为 0、3、4、2、1、5 则会方便很多。这就是离散化的思想,就是将离散的事物进行重新分配。
离散化方法:排序+二分
(推荐使用本方法)
基本原理就是排序后使用STL中的unque()
函数来获取整体数据不同元素的个数,然后在已排序序列二分查找 num[i] 的值,从而得到对 num[i] 对应的值,然后进行重新赋值。
for(int i = 0; i < n; i++){
scanf("%d", &num[i]);
disc[i] = num[i]; // num:原数据数组,disc:离散化后的数组
}
sort(disc, disc + n);
cnt = unique(disc, disc + n) - disc; // STL中的unique函数,具体内容见👇
for(int i = 0; i < n; i++)
num[i] = lower_bound(disc, disc + n, num[i]) - disc;
unique(a, b)
函数:STL中比较常见的函数,他的功能是“删除”序列中所有相邻的重复元素(只保留一个),因为只是处理相邻的重复元素所以在使用这个函数之前要进行排序。(此处略去更具体的都能再写一页博客的内容)。其中参数a
,b
为指针,类似sort()
函数中的参数。
lower_bound(a, b, v)
函数:二分查找返回a
、b
指针之间空间中大于等于 v 的第一个迭代器。
离散化方法:排序+暴力
#include <bits/stdc++.h>
#define MAX_N 1e5+5 // 根据实际问题调整
struct Node{
int data;
int index;
}num[MAX_N];
bool cmp(Node a, Node b){
return a.data < b.data;
}
int rank[MAX_N], n;
int main(){
scanf("%d", &n);
for(int i = 0;i < n; i++){
scanf("%d", &num[i].data);
num[i].index = i;
}
sort(num, num + n, cmp);
for(int i = 1; i <= n; i++){
rank[num[i].id] = i;
}
return 0;
}
排序之后按照原顺序进行赋值,相同元素就会出现离散化不成同一元素的情况,所以不推荐这种方法。
听大佬说洛谷P1955是一道有关离散化的题,我这个蒟蒻还没有做。🙃
有时间做了再搞题解什么的。🙃
题解我搞出来了,传送门:🚪