奶牛过马路(思维+排序)

题目

将每条路线按照a的大小进行排序。

从前往后考虑

        如果第i条线的bi大于Max(表示前i-1条线中最大的b)，那么说明此时第i条线未与其他线相交，标记该线。

从后往前考虑

        如果第i条线的bi大于Max(表示后n-i条线中最小的b)，那么说明此时第i条线未与其他线相交，标记该线。

两种情况都被标记的线的数量就是答案。

#include
using namespace std;
const int N=100010;

struct E
{
	int a,b;
}e[N];
bool st[N];


bool comp(struct E x1,struct E x2)
{
	return x1.a>n;
	for(int i=1;i<=n;i++)
		cin>>e[i].a>>e[i].b;
	
	sort(e+1,e+1+n,comp);
	
	int Max=-1*(1e7),Min=1e7,cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(Max=1;i--)
	{
		if(Min>e[i].b)
		{
			Min=e[i].b;
			if(st[i])
				cnt++;
		}
	}
	
	cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702471.html