离散化思想
离散化
离散化适合在数据范围很大但是又只使用部分数据的时候使用
例题 ： AcWing 103
离散化函数：
sort(a, a + n);
for(int i = 0; i < n; i ++ ) {
if(i == 0 || a[i] != a[i-1]) {
b[m++] = a[i];
}
}
//排序后进行离散化
int query (int x) {
return low_bound(b, b + m, x) - b;
}
//查找数据映射到哪个整数上了
离散化概念：
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；
— 来自 《百度百科》
简单的来说就是一个把元素映射的过程，以减小数据范围，方便进行计算。
常用在不关注数据本身的题目
小技巧：
//简便的for循环
#define _for(i, a, b) for(int i = (a); i < (b); i ++ )
#define _rep(i, a, b) for(int i = (a); i <= (b); i ++ )
//sort的cmp函数
struct movie {
int first, second;
}
bool cmp(movie m1, movoie m2) {
if(m1.first == m2.first) return m1.second > m2.second;
return m1.first > m2.first;
}
版权声明：本文为foolshao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。