蓝桥杯备考：离散化详解

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

比如这道题，我们应该开一个差分数组，但是a，b之间的间隔可是太大了，难道我们要开一个2的三十二次方大小的数组吗？我们也是开不了这么大的数组的

我们就需要把这些数离散化，映射到一个小于n的数组里面

比如[99,9,9999,999999,99,9]

如果我们要直接映射到一个哈希表上就要开一个10的6次方大小的数组，但是我们不用这么做

这种数据量小但是数据范围大的情况，我们可以把它从小到大依次映射

9就是编号1，99就是编号2，9999就是编号3，999999就是编号4

这种就是叫做我们的离散化

实现我们的离散化有两种方法，一种就是排序+去重+二分

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], disc[N];
int n;
int pos;
int find(int x)
{
	int l = 1, r = pos;
	while (l < r)
	{
		int mid = (l + r) / 2;
		if (disc[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		disc[++pos] = a[i];
	}
	sort(disc + 1, disc + 1 + pos);
	pos = (unique(disc + 1, disc + 1 + pos) - (disc + 1));
	for (int i = 1; i <= n; i++)
	{
		cout << a[i] << "离散化后是：" << find(a[i]) << endl;
	}


	return 0;
}

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

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int a[N],disc[N];
int main()
{
	int pos = 0;
	cin >> n;
	for(int i =1;i<=n;i++)
	{
		cin >> a[i];
		disc[++pos] = a[i];
	}
	sort(disc+1,disc+1+pos);
	unordered_map <int,int> mp;
	int cnt = 0;
	for(int i = 1;i<=pos;i++)
	{
		int x = disc[i];
		if(mp.count(x)) continue;
		++cnt;
		mp[x] = cnt;
	}
	for(int i= 1;i<=n;i++)
	{
		cout << a[i] << "离散化之后的值:" << mp[a[i]] << endl;
	}
}

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

我们把每个数都离散化，然后遍历每个区间，用差分数组对离散化后的区间进行整体+1

然后还原差分数组，统计每个区间（这时候区间个数要用原数据来算）

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 2e4+10;
int a[N],b[N];
int f[N*2],disc[N*2];
unordered_map<int,int> mp;
int n;
int pos;
int main()
{
	cin >> n;
	for(int i = 1;i<=n;i++)
	{
		cin >> a[i] >> b[i];
		disc[++pos] = a[i];
		disc[++pos] = b[i];
	}
	sort(disc+1,disc+1+pos);
	pos = unique(disc+1,disc+1+pos)-(disc+1);
	for(int i =1;i<=pos;i++)
	{
		mp[disc[i]] = i;
	}
	for(int i = 1;i<=n;i++)
	{
		int l = a[i],r = b[i];
		f[mp[l]]+=1;f[mp[r]]-=1;
	}
	for(int i = 1;i<=pos;i++)
	{
		f[i]+=f[i-1]; 
	}
	int ret = 0;
	for(int i = 1;i<=pos;i++)
	{
		int j = i;
		while(f[j]!=0 && j<=pos)
		{
			j++;
		}
		ret+=disc[j]-disc[i];
		i = j+1;
		
	}
	cout << ret << endl;
	return 0;
}