ACM 离散化处理

时间:2022-08-19 06:15:13

使用STL算法离散化: 

思路:先排序,再删除重复元素,然后就是索引元素离散化后对应的值。 

1.  unique():      

头文件为algorithm

unique的作用是“去掉”容器中相邻元素的重复元素(不一定要求数组有序),它会把重复的元素添加到容器末尾(所以数组大小并没有改变),而返回值是去重之后的尾地址.由于返回的是容器末尾,所以如果想得到去重后的size,需要减去初始地址用法:sz = unique(a ,a + n)-a; sz为容器大小

unique()是C++标准库函数里面的函数,其功能是去除相邻的重复元素(只保留一个),所以使用前需要对数组进行排序
上面的一个使用中已经给出该函数的一个使用方法,对于长度为n数组a,unique(a,a+n) - a返回的是去重后的数组长度
那它是怎么实现去重的呢?删除?
不是,它并没有将重复的元素删除,而是把重复的元素放到数组的最后面藏起来了
当把原长度的数组整个输出来就会发现:
代码如下:
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 
 7 int n ;
 8 int a[1000];
 9 int main()
10 {
11             cin>>n;      
12               for (int i = 0;i < n;++i)  
13           {     
14             scanf("%d",&a[i]);                         
15           }        
16          sort(a,a+n);    
17         int k = unique(a,a+n) - a;    
18             for (int i = 0;i < n;++i)     
19          {          
20                printf("%d ",a[i]);     
21            }    
22     
23      return 0 ;
24 }

输出的数组如下:

ACM 离散化处理

其中 1 2 8 9 10就是去重后的数组,我这里把后面“藏起来”的数也输出了,方便理解

 
2、 lower_bound() 函数
前闭后开区间进行二分查找函数lower_bound()在first和last中的前闭后开区间进行二分查找
返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置。
一个数组number序列为:4,10,11,30,69,70,96,100.
设要插入数字3,9,111.pos为要插入的位置的下标则pos = lower_bound( number, number + 8, 3) - number,pos = 0.即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) - number, pos = 1,即number数组的下标为1的位置(即10所在的位置)。
pos = lower_bound( number, number + 8, 111) - number, pos = 8,即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。
所以,要记住:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置,且last的位置是越界的!
 
 
 
 
 
一般是这样用的
1、 unique;       返回去重后的容器长度;
ACM 离散化处理2\

2、lower_bound             返回插入元素的位置;

ACM 离散化处理