您现在的位置是:首页 >技术教程 >群岛大战(C++)网站首页技术教程

群岛大战(C++)

Sirius·Black 2024-06-17 10:48:56
简介群岛大战(C++)

英文题目:

Problem Statement

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

The i − t h i-th ith bridge connects the i − t h i-th ith island from the west and the ( i + 1 ) − t h (i+1)-th (i+1)th 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 i i: A dispute took place between the a i − t h a_i-th aith island from the west and the b i − t h b_i-th bith island from the west. Please make traveling between these islands with bridges impossible.

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

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.
2 ≤ N ≤ 1 0 5 2 leq N leq 10^5 2N105
1 ≤ M ≤ 1 0 5 1 leq M leq 10^5 1M105
1 ≤ a i < b i ≤ N 1 leq a_i < b_i leq N 1ai<biN
All pairs ( a i , b i ) (a_i, b_i) (ai,bi) are distinct.

Input

Input is given from Standard Input in the following format:

N M N M NM
a 1 a_1 a1 b 1 b_1 b1
a 2 a_2 a2 b 2 b_2 b2
: : :
a M a_M aM b M b_M bM

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

中文题目:

问题陈述

这里有 N N N岛屿,从西向东排列,由 N − 1 N−1 N1桥梁连接。

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

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

请求 i i i:在西面的 a i − t h a_i-th aith岛和西面的 b i − t h b_i-th bith岛之间发生了争端。请不要在这些岛屿之间搭桥。

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

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

约束

输入中的所有值都是整数。
2 ≤ N ≤ 1 0 5 2 leq N leq 10^5 2N105
1 ≤ M ≤ 1 0 5 1 leq M leq 10^5 1M105
1 ≤ a i < b i ≤ N 1 leq a_i < b_i leq N 1ai<biN
所有对 ( a i , b i ) (a_i, b_i) (ai,bi)都是不同的。
##输入
标准输入的输入格式如下:

N M N M NM
a 1 a_1 a1 b 1 b_1 b1
a 2 a_2 a2 b 2 b_2 b2
: : :
a M a_M aM b M b_M bM

输出

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

样本1

输入

5 2
14
2 5

输出

1

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

样本2

输入

9 5
18
27
3 5
4 6
7 9

输出

2

示例3

输入

5 10
1 2
1 3
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;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。