#include <iostream>
#include <algorithm>

using namespace std;

typedef struct interval
{
	short f;
	short l;
}inter;

bool cmp(inter x,inter y)
{
	return x.f<y.f || x.f==y.f && x.l<y.l;
}

inter a[20005];

int main()
{
	short n,i,m[5000]={0},j,k,r;
	short cnt,x,y;
	cin>>n;

	for(i=0,k=0;i<n;i++)
	{	
		scanf("%d%d",&x,&y);
		for(r=0;r<k;r++)//输入的时候一处理一部分包含的问题
		{
			if(x<=a[r].f && y>=a[r].l ) break;

			if(x>=a[r].f && y<=a[r].l ) 
			{
				a[r].f=x,a[r].l=y;
				break;
			}
		}
		if(r==k) a[k].f=x,a[k++].l=y;
	}

		n=k;

	 for(i=n-1;i>=0;i--)//处理包含的问题,把包含的提出，只留被包含的
	 {
		 for(k=i-1;k>=0;k--)
			 if(a[i].f<=a[k].f && a[i].l>=a[k].l) n--;
			 if(a[i].f>=a[k].f && a[i].l<=a[k].l)
			 {
				 a[k]=a[i];
				 n--;
			 }
	 }
		
     sort(a,a+n,cmp);//排序
	
	 m[0]=a[0].l-1;
	 m[1]=a[0].l;

	for(i=1,k=2;i<n;i++)//求最小元素
	{
		cnt=0;
		for(r=k-1;r>=0;r--)
		{
			if(m[r]>=a[i].f && m[r]<=a[i].l) cnt++;
			if(cnt==2 || m[r]<a[i].f) break;
		}
		r=cnt;
		if(cnt==2) continue;
		else 
		{
			for(j=a[i].l;j>=a[i].f;j--)
			{
				if(j==m[k]) continue;
					m[k+(1-cnt)]=j;
					cnt++;
				if(cnt==2) break;
			}
			k+=2-r;
		}
	}

	cout<<k<<endl;
	return 12;
}

• Re:wa了N次 大家给侧测试也能通过 谁能帮看下 修改了下 还wa (1300) ccnuzhang 2008-04-21 21:45:13