广州的一起做网站怎么样,丽水专业网站建设价格,app定制开发的公司,扬州专业外贸网站建设推广引入
离散化#xff0c;就是把一些很离散的点给重新分配。
举个例子#xff0c;如果一个坐标轴很长(1e10)#xff0c;给你1e4个坐标#xff0c;询问某一个点#xff0c;坐标比它小的点有多少。
很容易就知道#xff0c;对于1e4个点#xff0c;我们不必把他们在坐…引入
离散化就是把一些很离散的点给重新分配。
举个例子如果一个坐标轴很长(1e10)给你1e4个坐标询问某一个点坐标比它小的点有多少。
很容易就知道对于1e4个点我们不必把他们在坐标轴上的位置都表示出来因为我们比较有多少比它小的话只需要知道他们之间的相对大小就可以而不是绝对大小这就需要离散化。
而离散化又分为两种分为的两种是对于重复元素来划分的。第一种是重复元素离散化后的数字相同第二种就是不同。
第一种
其实就是用一个辅助的数组把你要离散的所有数据存下来。
然后排序排序是为了后面的二分。
去重因为我们要保证相同的元素离散化后数字相同。
再用二分把离散化后的数字放回原数组。
代码如下。
#includealgorithm // 头文件
//n 原数组大小 num 原数组中的元素 lsh 离散化的数组 cnt 离散化后的数组大小
int lsh[MAXN] , cnt , num[MAXN] , n;
for(int i1; in; i) {scanf(%d,num[i]);lsh[i] num[i];
}
sort(lsh1 , lshn1);
cnt unique(lsh1 , lshn1) - lsh - 1;
for(int i1; in; i)num[i] lower_bound(lsh1 , lshcnt1 , num[i]) - lsh;
注意事项
1.去重并不是把数组中的元素删去而是重复的部分元素在数组末尾去重之后数组的大小要减一
2.二分的时候注意二分的区间范围一定是离散化后的区间
3.如果需要多个数组同时离散化那就把这些数组中的数都用数组存下来
第二种
第二种方式其实就是排序之后枚举着放回原数组
用一个结构体存下原数和位置按照原数排序
我结构体里面写了个重载也可以写一个比较函数
最后离散化后数在rank[]rank[]里面
#includealgorithm
struct Node {int data , id;bool operator (const Node a) const {return data a.data;}
};
Node num[MAXN];
int rank[MAXN] , n;
for(int i1; in; i) {scanf(%d,num[i].data);num[i].id i;
}
sort(num1 , numn1);
for(int i1; in; i)rank[num[i].id] i;
总结
先送一道有离散化的题Luogu1955
很水的一道题解析在这NOI2015程序自动分析
用的最多的是第一种方法第二种方法感觉比较陌生不过还是需要学的。20190506第二种方法On啊第一种是nlogn的但是第二种方法只适用于无重复元素的。对于第一种方法当所有a[i]2e6这样子时可以开数组预处理一下每个数的位置也可以优化到nlogn预处理之后单次查询O1有的同学说那你a[i]2e6了直接开数组不就行了吗还要啥离散化但是你别忘了你万一是个二维数组呢怎么开比如这个题【CodeForces - 255C】。
转自https://blog.csdn.net/weixin_43061009/article/details/82083983
