[数据结构与算法]2.23 算法练习

区间选点

这是一道贪心题，之前我对贪心的认识很浅显，就认为是给了题目直接贪心，像这道题目还需要先排序

二维数组快速排序方法!!!

真的很重要

一开始我用的是冒泡排序法，代码较长而且时间复杂度较高，在网上查询了一些算法之后，发现使用sort 构造cmp函数，然后将数组转化为结构体使用比较方便且快捷
接下来写几个练练手

sort排序

1.用cmp控制一维数组升序和降序

#include<iostream>
#include<algorithm>

using namespace std;

bool cmp(int x,int y){
	return x>y;//这里可以把x看成前一个，y看作后一个，因此x>y时就是降序 
}

const int N=100;
int a[N];

int main(){
	
	int n;
	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	cout<<"排序前"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
		cout<<endl;
	
	//正常的默认升序排序 sort(a+1,a+1+n);
	sort(a+1,a+1+n,cmp);//利用cmp可以升序以及降序 
	
	cout<<"排序后"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
		cout<<endl;
	
	return 0;
} 

2. 对结构体（二维数组）排序

#include<iostream>
#include<algorithm>

using namespace std;


const int N=100;

struct node{
	int a,b;//定义节点，成员相当于二维数组的两个维度 
};

node q[N];//结构体数组，看作二维数组 

bool cmp(node x,node y){//注意这里要写node,作为元素类型 
	return x.b>y.b;//这里可以把x看成前一个，y看作后一个，因此x>y时就是降序 
					//.b就是比较第二个元素 
}

int main(){
	
	int n;
	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>q[i].a>>q[i].b; 
		
	cout<<"排序前"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<q[i].a<<" "<<q[i].b<<endl;
	
	//正常的默认升序排序 sort(a+1,a+1+n);
	sort(q+1,q+1+n,cmp);//利用cmp可以升序以及降序 
	
	cout<<"排序后"<<endl;
	
	for(int i=1;i<=n;i++)
		cout<<q[i].a<<" "<<q[i].b<<endl;
	
	return 0;
} 

3. 按照某个元素排列，如果相等，排另一个元素

bool cmp(node x,node y){
	if(x.b==y.b)
		return x.a<y.a;//如果右一样大，则排左升序
	
	return x.b<y.b;//按照右升序排列 
}

因为直接对二维数组的排序我也没怎么看懂，因此就利用结构体，结果都一样

算法题代码

/*
给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
1≤N≤10^5,
-10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
*/

/*
思路：
	尽管给出的区间顺序可能不是按照端点大小排列的，但是当你在纸上画出来的时候会发现区间是有些顺序的
	而且每次尽量取某个区间的最右边的点能够使得它可能会覆盖更多的点。
	因此思路为：
		将所给区间按照右端点排序，从第一个开始，取最右边的点，如果该点可以覆盖下一个区间，那么就继续找下一个区间
		直到该点无法覆盖当前区间，取当前区间的右端点再作为一个点，以此类推，直到最后一个区间 
*/ 

#include<iostream>
#include<algorithm>

using namespace std;

const int N=110000;
int n;
int a[N][2];

struct node{
	int a,b;
};

node q[N];

bool cmp(node x,node y){
	return x.b<y.b;
}


int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	 	cin>>q[i].a>>q[i].b;//存入左右端点
		 
	/*	 
	for(int j=0;j<n-1;j++){
		for(int i=1;i<=n-j-1;i++){
			if(a[i][1]>a[i+1][1]){
				int t=a[i][1];
				a[i][1]=a[i+1][1];
				a[i+1][1]=t;
				
				t=a[i][0];
				a[i][0]=a[i+1][0];
				a[i+1][0]=t;	
			}
		}
	}	 //将区间按照右端点排序 
	*/
	
	sort(q+1,q+1+n,cmp);
	
	int ans=1;
	
	
	for(int i=1;i<=n;i++){
		a[i][0]=q[i].a;
		a[i][1]=q[i].b;
	}
	//之前用的是a，于是就赋值了，后面没有修改成q 
	
	int p=a[1][1];//选取第一个区间最右侧的点 
	for(int i=1;i<=n;){
		while(p>=a[i][0]&&p<=a[i][1]){//当这个点在区间内 
			i++;
		} 
		//如果不在
		if(i>n)
			break;
		p=a[i][1];
		i++;
		ans++;
	}
	
	cout<<ans;
	
	return 0;
} 

最大不相交区间数量
最大不相交区间数量

做题情况

21min完成 自信满满交了 结果WA了
23min修改完成 AC

错误原因就是我排序的时候是按照左端点排序的。
正确的应该是按照右端点排序，如果按照左端点排序，会出现某个区间虽然左端点很小，但是区间很长，而我们向右找的时候则会损失很多空间。因此需要找最小的右端点，当右端点相同了，也不需要比较左端点了，因为下一个区间的选择与右端无关了。
区间问题一定要注意考虑按照左端点还是右端点排序！！！
另外要考虑当某一端端点相同时，另一端应该怎么选！！！

代码

/*
给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

输入格式
第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示可选取区间的最大数量。

数据范围
1≤N≤10^5,
-10^9≤ai≤bi≤10^9
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
*/


//我认为本题和区间选点很相似，因此采用同样的思路


#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;

struct node{
	int a,b;//左右端点 
};

node q[N];

bool cmp(node x,node y){
	if(x.b==y.b)
		return x.a<y.a;//如果右端点一样大，优先考虑左端点小的 
	
	return x.b<y.b;//按照右端点升序排列 
}

int main(){
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++)
		cin>>q[i].a>>q[i].b;
	
	int ans=1;
	
	sort(q+1,q+1+n,cmp);
	
	node m=q[1];//当前选择的区间 
	
	for(int i=2;i<=n;){
		if(q[i].a>m.b){//如果某个区间（按左端点从小到大查找的）的左端点大于现在区间的右端点，那么可以选择 
			m=q[i];//选择区间
			ans++;//答案增加 
		}
		i++;//无论区间是否满足都要遍历下一个 
	}
	
	cout<<ans<<endl;
	
	return 0;
}