lower_bound实现离散化

今天学习了一些新的东西，我也不知道该怎么说，突然发现离散化居然可以这么玩，还是非常有意思的，下面我先放一个传统的离散化代码，没有学过的同学们相信经过一番脑补也应该可以知道这个东西是用来干什么的，但是这不是我们今天的重点！

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct sd{
    int val,loc;//val是值 loc是当前点的位置 
}x[100005]; 
bool cmp(sd a,sd b)
{
    if(a.val<b.val)
    return true;
}
int discretization[100005];//这单词真够长 
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>x[i].val;
        x[i].loc=i;
    }
    sort(x+1,x+n+1,cmp);
    int cnt=0; 
    x[0].val=891881292;//important!
    for(int i=1;i<=n;++i)
    {
        if(x[i-1].val==x[i].val)discretization[x[i].loc]=cnt;
        else 
        {
            cnt++;
            discretization[x[i].loc]=cnt;
        }
    } 
    for(int i=1;i<=n;++i)
    {
        cout<<discretization[i]<<" ";
    }
    return 0;
} 

是不是感觉思路虽然简单但是代码特别长······

所以今天我们的重点出来了如何用lower_bound来实现离散化操作。

没学过lower_bound的小朋友请戳这里☞lower_bound与upper_bound的使用注意事项

说白了一句话总结一下就是lower_bound返回的就是当前你要查找元素的第一个位置（注意：已经是排好了顺序的哦！！！）

所以说我们在这里实现这个操作就比较简单了，我们先把原数组复制到一个新的数组中，然后对新的数组实现排序和去重（没有学过去重吗？戳这里☞去重unique）的工作，最后我们把原数组中的每一个树依次用lower_bound来搜索他在新数组中的位置，最后我们在用这个位置信息更新一下原数组，那么一个离散化的操作就这样完成了，我再也不用写结构体啦！哈哈！

实现代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int arr[N];
int xs[N],cnt=-1;
int n;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>arr[i];
        cnt++;
        xs[cnt]=arr[i];
    } 
    sort(xs,xs+cnt);
    int e=unique(xs,xs+cnt)-xs;
    for(int i=1;i<=n;++i)
    {
        arr[i]=lower_bound(xs,xs+e,arr[i])-xs+1;  
    }
    for(int i=1;i<=n;++i)
    {
        cout<<arr[i]<<" "; 
    }
} 

谢谢采纳！