蓝桥杯备考：离散化详解

首先，为什么要有离散化呢？

比如这道题，我们应该开一个差分数组，但是a，b之间的间隔可是太大了，难道我们要开一个2的三十二次方大小的数组吗？我们也是开不了这么大的数组的
我们就需要把这些数离散化，映射到一个小于n的数组里面
比如[99,9,9999,999999,99,9]
如果我们要直接映射到一个哈希表上就要开一个10的6次方大小的数组，但是我们不消这么做
这种数据量小但是数据范围大的情况，我们可以把它从小到大依次映射
9就是编号1，99就是编号2，9999就是编号3，999999就是编号4
这种就是叫做我们的离散化
实现我们的离散化有两种方法，一种就是排序+去重+二分

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. const int N = 1e5 + 10;
5. int a[N], disc[N];
6. int n;
7. int pos;
8. int find(int x)
9. {
10.         int l = 1, r = pos;
11.         while (l < r)
12.         {
13.                 int mid = (l + r) / 2;
14.                 if (disc[mid] >= x) r = mid;
15.                 else l = mid + 1;
16.         }
17.         return l;
18. }
19. int main()
20. {
21.         cin >> n;
22.         for (int i = 1; i <= n; i++)
23.         {
24.                 cin >> a[i];
25.                 disc[++pos] = a[i];
26.         }
27.         sort(disc + 1, disc + 1 + pos);
28.         pos = (unique(disc + 1, disc + 1 + pos) - (disc + 1));
29.         for (int i = 1; i <= n; i++)
30.         {
31.                 cout << a[i] << "离散化后是：" << find(a[i]) << endl;
32.         }
35.         return 0;
36. }

复制代码

另一种方法就是利用哈希表unordered_map  map是双元的，第一个int存原始值，第二个int存离散化之后的值，我们就直接从小到大遍历dict数组，把每个原始值都编上号，重复的不编，然后我们再遍历原数组，通过原始值找对应的编号（这里直接下标访问就行了）

1. #include <iostream>
2. #include <unordered_map>
3. #include <algorithm>
4. using namespace std;
5. const int N = 1e5+10;
6. int n;
7. int a[N],disc[N];
8. int main()
9. {
10.         int pos = 0;
11.         cin >> n;
12.         for(int i =1;i<=n;i++)
13.         {
14.                 cin >> a[i];
15.                 disc[++pos] = a[i];
16.         }
17.         sort(disc+1,disc+1+pos);
18.         unordered_map <int,int> mp;
19.         int cnt = 0;
20.         for(int i = 1;i<=pos;i++)
21.         {
22.                 int x = disc[i];
23.                 if(mp.count(x)) continue;
24.                 ++cnt;
25.                 mp[x] = cnt;
26.         }
27.         for(int i= 1;i<=n;i++)
28.         {
29.                 cout << a[i] << "离散化之后的值:" << mp[a[i]] << endl;
30.         }
31. }

复制代码

我们回到火烧赤壁这道题来，apprently这道题是要用差分做的，但是如果我们直接差分的话，这个区间可以到达最大是2^32 我们是开不了这么大的数组的，所以我们就要用到所谓离散化

我们把每个数都离散化，然后遍历每个区间，用差分数组对离散化后的区间进行整体+1
然后还原差分数组，统计每个区间（这时候区间个数要用原数据来算）

1. #include <iostream>
2. #include <unordered_map>
3. #include <algorithm>
4. using namespace std;
5. const int N = 2e4+10;
6. int a[N],b[N];
7. int f[N*2],disc[N*2];
8. unordered_map<int,int> mp;
9. int n;
10. int pos;
11. int main()
12. {
13.         cin >> n;
14.         for(int i = 1;i<=n;i++)
15.         {
16.                 cin >> a[i] >> b[i];
17.                 disc[++pos] = a[i];
18.                 disc[++pos] = b[i];
19.         }
20.         sort(disc+1,disc+1+pos);
21.         pos = unique(disc+1,disc+1+pos)-(disc+1);
22.         for(int i =1;i<=pos;i++)
23.         {
24.                 mp[disc[i]] = i;
25.         }
26.         for(int i = 1;i<=n;i++)
27.         {
28.                 int l = a[i],r = b[i];
29.                 f[mp[l]]+=1;f[mp[r]]-=1;
30.         }
31.         for(int i = 1;i<=pos;i++)
32.         {
33.                 f[i]+=f[i-1];
34.         }
35.         int ret = 0;
36.         for(int i = 1;i<=pos;i++)
37.         {
38.                 int j = i;
39.                 while(f[j]!=0 && j<=pos)
40.                 {
41.                         j++;
42.                 }
43.                 ret+=disc[j]-disc[i];
44.                 i = j+1;
45.                
46.         }
47.         cout << ret << endl;
48.         return 0;
49. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。