题意理解

在一个数轴上,有$N$条线段,每条线段的起点为$T$,长度为$L$,求不相交的线段最多有几条。

算法分析

很简单的贪心。假设我们每次要选择终点为$E$的线段,当然是要使这个$E$尽可能小。因为当$E$最小的时候,你能选择的线段肯定会更多。

代码构造

分析过后,很明显我们要按结束时间从小到大排序。然后记录下上一次选择线段的终点,然后依次对比起点。

代码


#include <iostream>
#include <algorithm> 		//sort要用
using namespace std;
struct node{
	int strat;
	int end;				//这是终点,而不是长度
};							//结点结构体
bool cmp(node x,node y){
	return x.end<y.end;		//按照刚才分析的,要选择终点尽可能小的
}
node f[10005];
int n;
int ans;					//总共能选择多少条
int end;					//上一次选择线段的终点
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>f[i].strat;
		cin>>f[i].end;
		f[i].end+=f[i].strat;//将长度转化为终点
	}
	sort(f+1,f+n+1,cmp);	//排序
	ans=1;					//首先肯定要选择重点最近的那个,也就是f[i]
	end=f[1].end;			//终点设置
	for(int i=2;i<=n;++i){
		if(end<=f[i].strat){//如果之前选择的的终点小于等于现在的起点,也就是这两条线段不相交
			++ans;			//选择了
			end=f[i].end;	//更新end
		}
	}
	cout<<ans;
	return 0;
}

比较简单的一题贪心,稍加思考就可以想出来。

完结撒花✿

发表评论

邮箱地址不会被公开。