算法学习05：离散化、区间合并
文章目录
- 算法学习05：离散化、区间合并
- 前言
- 需要记忆的模版：
- 一、离散化
- 1.例题：离散化 + 区间和：
- 拓展:
- 二、区间合并（贪心）
- 1.例题：
- 总结
前言
需要记忆的模版：
vector<int> alls;//存储所有待离散化的值
sort(alls.begin(), alls.end());//将所有值排序
//去除重复的元素，并且不重复的元素 有序 的排在前面
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//找到有序的排在前面的 坐标 所对应的 索引
//返回 坐标 所对应的 映射
int find(int x)
{
int l = 0, r = alls.size() - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;//索引从0开始，映射后从1开始
}
//区间合并：
void merge(vector<PII> &segs)
{
vector<PII> res;
//按照 区间左端点 排序
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;//
for(auto seg : segs)
{
if(ed < seg.first)
{
//一个区间已经合并完了
if(st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;//更新
}
else ed = max(ed, seg.second());//判断 ed 是否要更新
}
//注意：无论是那种情况到最后，都还剩下一个 区间 没有加入到res中
if(st != -2e9) res.push_back({st, ed});
segs = res;
}
提示：以下是本篇文章正文内容：
一、离散化
1.例题：离散化 + 区间和：
例题：求区间和，区间长度无限长（无限长的数轴）
具体题目：假定有一个无限长的数轴，数轴上的每个坐标都是0，我们首先进行n次操作，每次操作将某一位置x上的数加c。
接下来进行m次询问，每次询问包含 l 和 r ，求区间[l，r]间所有数的和。
int main()
{
cin >> n >> m;
//插入n次数操作 --------- 先将数据存储起来
for(int i = 0; i < n; i ++)
{
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);//存储所有待 离散化 的值
}
//执行m次询问 --------- 先将数据存储起来
for(int i = 0; i < m; i ++)
{
int l, r;
cin >> l >> r;
query.push_back({l, r});
alls.push_back(l);//存坐标
alls.push_back(r);//存坐标
}
//***关键***
sort(alls.begin(), alls.end());//将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去除重复的元素，并且不重复的元素 有序 的排在前面
//注意：现在我们已经将 坐标 离散化了，而且 输入的数据 也已经存储好了。
//接下来，我们就要使用 “前缀和” 来求解 “区间和”
//原数组
for(auto item : add)
{
int x = find(item.first);
a[x] += item.second;
}
//前缀和数组
for(int i = 1; i <= alls.size(); i ++) s[i] = a[i] + s[i - 1];
//处理询问：
for(auto item : query)
{
int l = find(query.first()), r = find(query.second());
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
拓展:
//------ 拓展 ---------
//注意： vector<int> :: iterator 与 return a.begin() + j;
//迭代器 与 索引的关系？不清楚。
vector<int> :: iterator unique(vector<int> &a)
{
int j = 0;
for(int i = 0; i < a.size(); i ++)
if(!i && a[i] != a[i - 1]) a[j ++] = a[i];
return a.begin() + j;
}
二、区间合并（贪心）
1.例题：
例题：给n个区间，合并有交集的区间，求最后剩下的区间个数。
具体题目：给定n个区间[l i, r i]，要求合并所有有交集的区间，（注意：如果在端点出相交，也算有交集），最后输出合并完成后的区间个数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int , int> PII;
const int N = 100000 + 10;
int n;
vector<PII> segs;//存储合并完后的区间
void merge(vector<PII> &segs)
{
vector<PII> res;
//按照 区间左端点 排序
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;//
for(auto seg : segs)
{
if(ed < seg.first)
{
if(st != -2e9) res.push_back({st, ed});//一个区间已经合并完了
st = seg.first, ed = seg.second;//更新
}
else ed = max(ed, seg.second());//判断 ed 是否要更新
}
//注意：无论是那种情况到最后，都还剩下一个 区间 没有加入到res中
if(st != -2e9) res.push_back({st, ed});
segs = res;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
总结
提示：这里对文章进行总结：
💕💕💕
