『ACM-算法-离散化』信息竞赛进阶指南--离散化数据离散化是一个非常重要的思想。
为什么要离散化?
当以权值为下标的时候,有时候值太大,存不下。 所以把要离散化的每一个数组里面的数映射到另一个值小一点的数组里面去。 image.png
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。 例如:
原数据:12,9999,9000900,150;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};处理后:{3,4},{2,6},{1,5};
但是离散化仅适用于只关注元素之间的大小关系而不关注元素本身的值 // 离散化
void discrete() {
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) // 也可用STL中的unique函数 = a[i - 1])
b[++m] = a[i];
}
// 离散化后,查询x映射为哪个1~m之间的整数
void query(int x) {
return lower_bound(b +