离散化-白红宇

离散化

阅读量：5021 次

发布时间：2019-06-12

本文共 1285 字，大约阅读时间需要 4 分钟。

转：

方法一：

9 1 0 5 4 与 5 2 1 4 3 的逆序对个数相同。

设有4个数：

1234567、123456789、12345678、123456

排序：123456<1234567<12345678<123456789

=> 1 < 2 < 3 < 4

那么这4个数可以表示成：2、4、3、1

sort(sub_a,sub_a+n);

int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数

for(i=0;i

对于第3步，若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound，从1, 2, 3, ..., size则用upper_bound，其中lower_bound返回第1个不小于b[i]的值的指针，而upper_bound返回第1个大于b[i] 的值的指针，当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果，两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

方法二：

转：

假如有m个数（m较小），但是每个数的取值范围很大(0<=ai<=1000000000)。我想记录哪些数字出现过，应该怎么离散呢？我知道最基本的作法是开一个标记的数组，哪个数字出现，就让那个数字对应的下标数组变成1，但是范围太大，没可能开1000000000的数组来存放标记，那要怎么办？这里就应该是用STL中的map。把ai当成key，value随便都行，那么查询是否有这个数的时候使用map的函数count（key）就可以了。

#include 
     
      #include 
      #include 
       
        using namespace std;map 
        
          _map;int n,m;int main(){    while(cin >> n >> m)    {        int temp,a,b;        _map.clear();        for(int i = 1;i <= n;i++)        {            cin >> temp;            _map[temp] = 1;//随便给一个值就行        }        for(int i = 1;i <= m;i++)        {            cin >> b;            if(!_map.count(b))                cout << 0 << endl;            else                cout << _map[b] << endl;        }    }    return 0;}

转载于:https://www.cnblogs.com/ZP-Better/p/4715363.html

你可能感兴趣的文章