蓝桥杯备考：离散化详解
首先，为什么要有离散化呢？https://i-blog.csdnimg.cn/direct/36c4da9bce934c8aa5c54991d6fd7a3b.png
https://i-blog.csdnimg.cn/direct/4ee783b8af844c03bc51add75292364e.png
比如这道题，我们应该开一个差分数组，但是a，b之间的间隔可是太大了，难道我们要开一个2的三十二次方大小的数组吗？我们也是开不了这么大的数组的
我们就需要把这些数离散化，映射到一个小于n的数组里面
比如
如果我们要直接映射到一个哈希表上就要开一个10的6次方大小的数组，但是我们不消这么做
这种数据量小但是数据范围大的情况，我们可以把它从小到大依次映射
9就是编号1，99就是编号2，9999就是编号3，999999就是编号4
这种就是叫做我们的离散化
实现我们的离散化有两种方法，一种就是排序+去重+二分
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a, disc;
int n;
int pos;
int find(int x)
{
int l = 1, r = pos;
while (l < r)
{
int mid = (l + r) / 2;
if (disc >= x) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a;
disc[++pos] = a;
}
sort(disc + 1, disc + 1 + pos);
pos = (unique(disc + 1, disc + 1 + pos) - (disc + 1));
for (int i = 1; i <= n; i++)
{
cout << a << "离散化后是：" << find(a) << 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,disc;
int main()
{
int pos = 0;
cin >> n;
for(int i =1;i<=n;i++)
{
cin >> a;
disc[++pos] = a;
}
sort(disc+1,disc+1+pos);
unordered_map <int,int> mp;
int cnt = 0;
for(int i = 1;i<=pos;i++)
{
int x = disc;
if(mp.count(x)) continue;
++cnt;
mp = cnt;
}
for(int i= 1;i<=n;i++)
{
cout << a << "离散化之后的值:" << mp] << endl;
}
}
https://i-blog.csdnimg.cn/direct/ce1ae6c200b54b899c5e0b0a60562f3c.png
https://i-blog.csdnimg.cn/direct/c2f40726758541fb8d8784897b45fc6e.png
我们回到火烧赤壁这道题来，apprently这道题是要用差分做的，但是如果我们直接差分的话，这个区间可以到达最大是2^32 我们是开不了这么大的数组的，所以我们就要用到所谓离散化https://i-blog.csdnimg.cn/direct/9cee9a82c624452dbbabee5dbab14315.png
https://i-blog.csdnimg.cn/direct/40cc73ec119b46d2bae4a840a5c9752f.png
我们把每个数都离散化，然后遍历每个区间，用差分数组对离散化后的区间进行整体+1
然后还原差分数组，统计每个区间（这时候区间个数要用原数据来算）
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 2e4+10;
int a,b;
int f,disc;
unordered_map<int,int> mp;
int n;
int pos;
int main()
{
cin >> n;
for(int i = 1;i<=n;i++)
{
cin >> a >> b;
disc[++pos] = a;
disc[++pos] = b;
}
sort(disc+1,disc+1+pos);
pos = unique(disc+1,disc+1+pos)-(disc+1);
for(int i =1;i<=pos;i++)
{
mp] = i;
}
for(int i = 1;i<=n;i++)
{
int l = a,r = b;
f]+=1;f]-=1;
}
for(int i = 1;i<=pos;i++)
{
f+=f;
}
int ret = 0;
for(int i = 1;i<=pos;i++)
{
int j = i;
while(f!=0 && j<=pos)
{
j++;
}
ret+=disc-disc;
i = j+1;
}
cout << ret << endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]