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[1000];
int main()
{
            cin>>n;      
              for (int i = 0;i < n;++i)  
          {     
            scanf("%d",&a[i]);                         
          }        
         sort(a,a+n);    
        int k = unique(a,a+n) - a;    
            for (int i = 0;i < n;++i)     
         {          
               printf("%d ",a[i]);     
           }    
    
     return 0 ;
}

输出的数组如下：

其中 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\

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