离散化模板

作者： 作者的头像   Chicago ,  2019-02-09 15:28:49 ,  所有人可见 ,  阅读 3796

14


19

在很多情况下，问题的范围虽然定义在整数集合$Z$，但是只涉及其中$m$个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）。此时，我们就可以把整数集合$Z$中的这$m$个整数与$1～m$建立映射关系。

通俗来讲，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

算法流程

  • 预处理

  • 先将无序数组排序。

  • 去重。

  • 二分查找

知识拓展

  1. C++STL中的unique函数解析
  2. C++ lower_bound 与 upper_bound 函数

模板

//离散化预处理
inline void discrete()
{
    //排序
    sort(a + 1,a + n + 1);
    //去重
    for(int i = 1;i <= n;++i)
    {
        if(i == 1 || a[i] != a[i-1])
            b[++m] = a[i];
    }
}

//二分查找 x映射为那个1~m之间的整数
inline int query(int x)
{
    return lower_bound(b + 1,b + m + 1,x) - b;
}

5 评论

用户头像
潘瑞杰   2019-11-22 16:38         踩      回复

查找是为什么要 - b?

用户头像
做梦都ac   2023-04-14 23:24         踩      回复

通过返回的地址减去起始地址begin,得到找到数字在数组中的下标

用户头像
VictorDw   2019-03-13 00:29         踩      回复

++m是m从0开始吗

用户头像
Chicago   2019-03-14 19:27      1    踩      回复

自己运行一下这个程序你就懂了。

#include<bits/stdc++.h>
using namespace std;

int main(void)
{
    int m = 0;
    cout << m++ << endl;
    cout << m << endl;
    cout << endl;
    m = 0;

    cout << ++m << endl;
    cout << m << endl;
    cout << endl;
    m = 0;

    int num[3] = {0,0,0};

    num[m++] = 1234;
    for(int i = 0;i < 3;++i)
        cout << num[i] << " ";
    cout << endl;

    m = 0;
    for(int i = 0;i < 3;++i)
        num[i] = 0;

    num[++m] = 1234;
    for(int i = 0;i < 3;++i)
        cout << num[i] << " ";
    cout << endl;

    return 0;
 }
用户头像
Chicago   2019-02-09 15:30         踩      回复

有错误，或者不懂的可以在评论区提出。