先字符串排序，再建笛卡儿树，但还是time limited  exceed??????请问各位大哥是什么回事

#include <utility>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

bool operator<(const pair<string,int> &a1, const pair<string,int> &a2)
{
	return a1.first< a2.first;
}

struct node{
  pair<string,int> data;       
  node  *lchild, *rchild;
  node(){
	  lchild=NULL;
	  rchild=NULL;
  } 
};

class treap{
private:
    node  *root;         //指向根结点的头指针
public:
	treap(){
		root=NULL;
	}
	treap(node *n){
		root=n;
	}
	void insert(node * n);
	void print_tree();
	void print_node(node * n);
};

void treap::print_tree()
{
	print_node(root);
}
void treap::print_node(node *n){
	if(n!=NULL)
	{
		cout<<"(";
		print_node(n->lchild);
		cout<<n->data.first<<"/"<<n->data.second;
		print_node(n->rchild);
		cout<<")";
	}

}

void treap::insert(node * n)
{
	node * insert_pos;
	node * insert_pos_parent;
	node * index;
//	bool is_found;

	if (root==NULL)
	{
		root=n;
		return;
	}
		
	index=root;
	insert_pos_parent=NULL;
	insert_pos=NULL;
	
	while(index!=NULL)
	{
		if(index->data.second < n->data.second){
			insert_pos=index;
			break;
		}
		insert_pos_parent=index;	
		index=index->rchild;		
	}
	if(insert_pos_parent==NULL)
	{
		n->lchild=root;
		root=n;
		return;
	}
	insert_pos_parent->rchild=n;
	n->lchild=insert_pos;

}
int main()
{
	int count,i,number;
	string str;
	char c;
	pair<string,int> a[50000];

	while (1)
	{
		cin>>count;
		if(count==0)
			break;

		for(i=0; i<count; i++)
		{
			str="";
			while(cin>>c)
			{
				if(c!='/')
					str+=c;
				else{
					cin>>number;					
					a[i]=make_pair(str,number);
					break;
				}			
			}
		}
		sort(a,a+count);
/*		for (i=0;i<count;i++)
		{
			cout<<a[i].first<<"**"<<a[i].second<<"  ";
		}
		cout<<endl;
*/
		treap tp;
		for (i=0;i<count;i++)
		{
			node *n=new node();
			n->data=a[i];
			tp.insert(n);
		}
		tp.print_tree();
		cout<<endl; 
	}
}

	

• 不会笛卡尔＝＝字符排序＋数字RMQ＋DFS (2303) winsweet 2008-08-28 13:37:08