离散化小记

感觉现在写个啥都得搞离散化orz
目前已知的离散化方式:
1.手写多累,用map啊(可能会被卡掉)
map<int,int>即可
2.vector离散化(应该没有手写快,不过一般不会被卡)
我们将要离散化的所有数存进vector里,排序。查询一个数被离散化之后的值用lower_bound即可

for(int i=1;i<=n;i++)
 a[i]=read(),vec.push_back(a[i]);//vec就是定义的vector
sort(vec.begin(),vec.end());
for(int i=1;i<=n;i++)
 a[i]=lower_bound(vec.begin(),vec.end(),c)-vec.begin()+1;//下标从1开始

3.参照vector离散化的思路,手写离散化
就是把所有元素存进一个数组里(在你知道上限的情况下),排序,手写lower_bound即可

int n,be[N],ae[N],t;//N根据题目确定
int lower_bound(int kkk)
{
    int ll=1,rr=t;
    while(ll<=rr)
    {
        int mid=(ll+rr)>>1;
        if(ae[mid]==kkk) return mid;
        if(ae[mid]>kkk)rr=mid-1;
        else ll=mid+1;
    }
    if(ae[ll]>kkk)ll--;//写丑了的lower_bound
    return ll;
}
int main()
{
   for(int i=1;i<=n;i++)
   {
    be[i]=read();ae[i]=be[i];
   }
   sort(ae+1,ae+1+n);
   t=unique(ae+1,ae+1+n)-ae-1;
   for(int i=1;i<=n;i++)
    be[i]=lower_bound(be[i]);
}

虽然费事,但跑的快

上一篇:Invalid bound statement (not found):


下一篇:Gyn 100989 "1D Cafeteria (B)"(set+lower_bound)