ACM 离散化处理

使用STL算法离散化：

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

1. unique():

头文件为algorithm

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

unique()是C++标准库函数里面的函数，其功能是去除相邻的重复元素（只保留一个），所以使用前需要对数组进行排序

上面的一个使用中已经给出该函数的一个使用方法，对于长度为n数组a，unique(a,a+n) - a返回的是去重后的数组长度
那它是怎么实现去重的呢？删除？
不是，它并没有将重复的元素删除，而是把重复的元素放到数组的最后面藏起来了
当把原长度的数组整个输出来就会发现：

代码如下：

 #include<iostream>

 #include<stdio.h>

 #include<algorithm>

 using namespace std;

 int n ;

 int a[];

 int main()

 {

             cin>>n;

               for (int i = ;i < n;++i)

           {

             scanf("%d",&a[i]);

           }

          sort(a,a+n);

         int k = unique(a,a+n) - a;

             for (int i = ;i < n;++i)

          {

                printf("%d ",a[i]);

            }    

      return  ;

 }

输出的数组如下：

其中 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; 返回去重后的容器长度；

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

巴特西

ACM 离散化处理

最新文章

热门文章