算法学习05：离散化、区间合并

算法学习05：离散化、区间合并

---

---

前言

需要记忆的模版：

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

---

提示：以下是本篇文章正文内容：

一、离散化

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;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

---

---

拓展:

//------ 拓展 ---------
 //注意： 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
2
3
4
5
6
7
8
9
10
11

---

---

---

二、区间合并（贪心）

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;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

---

总结

提示：这里对文章进行总结：