这题为啥不可以以右端点为第一关键字排序呢?
查看原帖
这题为啥不可以以右端点为第一关键字排序呢?
211144
waOooo楼主2020/6/10 22:56

rt,求路过的大佬指点一下!疯狂爆0了。

struct Node{
	int l,r;
}qu[N]; 
bool cmp(Node p,Node q){
	if(p.r==q.r) return p.l<q.l;
	return p.r<q.r;
}
vector<pa>ans;
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>qu[i].l>>qu[i].r;
	sort(qu+1,qu+n+1,cmp);
	int L=qu[1].l,R=qu[1].r;
	for(int i=2;i<=n;i++){
		if(qu[i].l>qu[i-1].r){
			ans.push_back(pa(L,R));
			L=qu[i].l,R=qu[i].r;
		}
		else R=qu[i].r,L=min(L,qu[i].l);
	}
	ans.push_back(pa(L,R));
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl; 
	return 0;
}
2020/6/10 22:56
加载中...