一、离散化
介绍
照片要曾经说过：“你们这再优化，也比不过我离散化的速度。”
可以看出离散化再一些题目中还是十分吃香的。百度百科上是这样解释离散化的：
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：{ \(1,999,100000,15\) }；处理后：{ \(1,3,4,2\) }；
原数据：{ \(100,200\) }，{ \(20,50000\) }，{ \(1,400\) }；
处理后：{ \(3,4\) }，{ \(2,6\) }，{ $ 1,5$ }；
所以说，离散化是改变了数据的具体数值的，那么也就表明，离散化适用于不在乎数据的具体大小，只需利用数据间相对大小即可求解的情况。
离散化又分为两种，第一种是重复的元素离散化后的数字还是相同的，第二种就是离散化后数字不同。
第一种
int a[20], b[20];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], b[i]=a[i]; //原数组a[]，离散化后的数组b[]
sort(a + 1, a + 1 + n);
int len = unique(a + 1, a + 1 + n) - a - 1;
for (int i = 1; i <= n; i++)
b[i] = lower_bound(a + 1, a + len + 1, b[i]) - a;
for (int i = 1; i <= n; i++)
cout << b[i] << ' ';
return 0;
}
/*
输入：
5
1114 555 34789 22456 114514
输出：
2 1 4 3 5
*/
第二种
第二种就比较简单了，就是利用结构体排序，排完后直接存到离散化后的数组里即可：
struct node {
int val, id;
friend bool operator <(node x1, node x2) {
return x1.val < x2.val; //根据需要来判断是大根堆还是小根堆
}
}
a[20];
int n;
int b[20];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].val;
a[i].id = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
b[a[i].id] = i;
for (int i = 1; i <= n; i++)
cout << b[i] << ' ';
return 0;
}
/*
输入：
5
114 114 33 514 1919810
输出：
2 3 1 4 5
*/
以上就是离散化的两种实现方式，一定要仔细观察代码片段中的各个细节，发现其中的精髓。
…………
我才不会告诉你数组有b20