基础思维——离散化（附例题）

引论

离散化：
把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。具体来说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
–
例如：
原数据：1,999,100000000000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；
–
例如：
在一个坐标轴很长(>1e8)，给你1e4个坐标，询问某一个点，坐标比它小的点有多少。我们只需要知道他们之间的相对大小就可以，这就需要离散化。

两种离散化方法（去重与不去重）

1、离散化——去重

理解思路
①、在 book 数组中记录出现的元素大小 tot。
②、对 book 数组进行从小到大排序，利用 unique函数对 book 数组进行去重，得到去重后的数组大小 c 。

//unique(book,book+n);
//前一个是当序列的相邻的数据相同时，删除相邻相同的数字。
sort(book, book+tot);
//必须先排序
int c = unique(book, book+tot) - book;

③、再对 book 数组进行从小到大排序，在 book 数组下找原数组 num 对应的下标即为离散数组 ans。

for (int i=0; i<n; i++) { 
   
    ans[i] = lower_bound(book, book+c, num[i])-book;
}

离散化——去重：整合代码

#include<bits/stdc++.h>
using namespace std;
int ans[100010]={ 
   0};//离散化后数组
int num[100010], book[100010];
int n;

int main(){ 
   
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; i++) { 
   
	    scanf("%d",&num[i]);
	    book[i] = num[i];
	}
	 
	int c = unique(book, book+n) - book;
	sort(book , book