群岛大战（C++）-Toy模板网

这篇具有很好参考价值的文章主要介绍了群岛大战（C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

英文题目：

Problem Statement

There are $N$ islands lining up from west to east, connected by $N - 1$ bridges.

The $i - t h$ bridge connects the $i - t h$ island from the west and the $(i + 1) - t h$ island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request $i$ : A dispute took place between the $a_i-th$ island from the west and the $b_i-th$ island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these $M$ requests.

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.
$\leq N \leq 10^5$
$\leq M \leq 10^5$
$\leq a_i < b_i \leq N$
All pairs $a_i, b_i)$ are distinct.

Input

Input is given from Standard Input in the following format:

$NM$
$a_1$ $b_1$
$a_2$ $b_2$
$:$
$a_M$ $b_M$

Output

Print the minimum number of bridges that must be removed.

Sample 1

Input

5 2
1 4
2 5

Output

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Sample 2

Input

9 5
1 8
2 7
3 5
4 6
7 9

Output

2

Sample 3

Input

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Output

4文章来源地址https://www.toymoban.com/news/detail-451775.html

中文题目：

问题陈述

这里有 $N$ 岛屿，从西向东排列，由 $N - 1$ 桥梁连接。

$i - t h$ 桥连接了西面的 $i - t h$ 岛和西面的 $(i + 1) - t h$ 岛。

一天，一些岛屿之间发生了争端，岛上的居民提出了M个请求:

请求 $i$ :在西面的 $a_i-th$ 岛和西面的 $b_i-th$ 岛之间发生了争端。请不要在这些岛屿之间搭桥。

您决定删除一些桥以满足所有这些 $M$ 请求。

找出必须拆除的桥的最小数量。

约束

输入中的所有值都是整数。
$\leq N \leq 10^5$
$\leq M \leq 10^5$
$\leq a_i < b_i \leq N$
所有对 $a_i, b_i)$ 都是不同的。
＃＃输入
标准输入的输入格式如下:

$NM$
$a_1$ $b_1$
$a_2$ $b_2$
$:$
$a_M$ $b_M$

输出

打印必须移除的桥的最小数量。

样本1

输入

5 2
14
2 5

输出

1

通过拆除连接西部第二和第三岛屿的桥梁，可以满足这些要求。

样本2

输入

9 5
18
27
3 5
4 6
7 9

输出

2

示例3

输入

5 10
１２
１３
14
15
2 3
2 4
2 5
3 4
3 5
4 5

输出

4

代码

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y; } a[1200000];
int n,m,s,mi; 
bool cmp(node a,node b)
{
	if(a.y==b.y)
		return a.x<b.x;
	return a.y<b.y;
}
int main() 
{
	cin >>n >>m;
	for (int i=1;i<=m;i++)
	{
		cin >>a[i].x >>a[i].y;
		mi=min(mi,a[i].y);
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(a[i].x>=mi)
		{
			s++;
			mi=a[i].y;
		}
	}
	cout <<s;
	return 0;
}