那位大牛在线，帮忙看下程序，具体的函数功能看函数名应该就能看明白。我TLE了好久了，本地生成的数据都过得了，时间不卡，但是。。。。不知道是不是由于特殊数据陷入了死循环。大牛帮帮忙啊。。。。


#include<stdio.h>
//#include<time.h>
//#include<fstream.h>
//#include   <dos.h>   
//#include<algorithm>
//using namespace std;
const int N=50000;
const int M=999999999;
struct node
{
	int l,r,b,e,min;
}tree[2*N+5];
struct node2
{
	int a,b;
}data[N+5];
int tnum;
void build(int b,int e,int v)//建从b到e的线段树，根在tree[v]
{
	int now=v;
	tnum++;
	tree[v].b=b;tree[v].e=e;tree[v].min=M;
	if(b<e)
	{
		tree[now].l=tnum+1;
		build(b,(b+e)/2,tree[now].l);
		tree[now].r=tnum+1;
		build((b+e)/2+1,e,tree[now].r);
	}
	else tree[now].l=tree[now].r=0;
}
void insert(int e,int v,int min)
{
	if(min<tree[v].min)tree[v].min=min;
	if(tree[v].l==0)return;
	else 
	{
		int mid=(tree[v].b+tree[v].e)/2;
		if(e<=mid)insert(e,tree[v].l,min);
		else insert(e,tree[v].r,min);
	}
}
int getmin(int l,int r,int v)
{
	if(tree[v].b>=l&&tree[v].e<=r)return tree[v].min;
	int mid=(tree[v].b+tree[v].e)/2;
	int m1=M,m2=M;
	if(l<=mid)m1=getmin(l,r,tree[v].l);
	if(r>mid)m2=getmin(l,r,tree[v].r);
	/*	if(r<=mid)return getmin(l,r,tree[v].l);
	else if(l>mid)return getmin(l,r,tree[v].r);
	m1=getmin(l,r,tree[v].l);
	m2=getmin(l,r,tree[v].r);*/
	if(m1>m2)return m2;
	else return m1;
}
int main()
{
//	ifstream  fin("out.txt");
	int n,m;
//		long t0,t1;
//			t0=clock();
	while(scanf("%d%d",&n,&m)!=EOF)
//	(fin>>n>>m)
	{
		tnum=0;
		build(1,n,1);
		insert(1,1,0);
		int i;
		for(i=0;i<m;i++)
		{
					scanf("%d%d",&data[i].a,&data[i].b);
//			fin>>data[i].a>>data[i].b;
			if(data[i].a<data[i].b)
			{
				int min=getmin(data[i].a,data[i].b-1,1);
				insert(data[i].b,1,min+1);
			}
		}
		//	delay(2000);
		
		printf("%d\n",getmin(n,n,1));
	}
//		t1=clock();
//	printf("%d\n",t1-t0);
	return 0;
}

• 没有大牛帮着看看吗？？感激不尽 (2023) y07yangruilong 2008-03-13 20:46:30