> 先说一个问题：开始我只开到5000，TLE了，后来我发现问题的规模是50000。为什么5000的时候没有RTE呢？是不是测试数据小于5000的啊？如何这样都TLE，那么我没想法了。
> //#include<fstream>
> #include<iostream>
> #include<algorithm>
> using namespace std;
> 
> class Node{
> public:
> 	int p,a,k;
> 	Node(){}
> 	Node(int pp,int aa,int kk):p(pp),a(aa),k(kk){}
> 	friend bool operator<(const Node& aa,const Node& bb){
> 		return aa.k<bb.k;
> 	}
> };
> 
> Node * nodes;
> int tree[50000][3];
> 
> int DC(int low,int high,int father){
> 	if(low==high)return 0;
> 	int mina=40000,mink,minp,mini;
> 	if(high-low==1){
> 		mini=nodes[low].p;
> 		tree[mini-1][1]=0;
> 		tree[mini-1][2]=0;
> 		tree[mini-1][0]=father;
> 		return mini;
> 	}
> 	//找到含有最小a的元素
> 	int i;
> 	for(i=low;i<high;++i)
> 		if(mina>nodes[i].a){
> 			minp=i;
> 			mina=nodes[i].a;
> 			mink=nodes[i].k;
> 			mini=nodes[i].p;
> 		}
> 	//递归处理左右子树，排序之后已经保证left<root<right了
> 	int left=DC(low,minp,mini);
> 	int right=DC(minp+1,high,mini);
> 	tree[mini-1][1]=left;
> 	tree[mini-1][2]=right;
> 	tree[mini-1][0]=father;
> 	return mini;
> }
> 
> 
> int main(){
> 	//ifstream cin("in.txt");
> 	int n;
> 	cin>>n;
> 	nodes=new Node[n];
> 	int i,a,k;
> 	for(i=0;i<n;i++){
> 		cin>>k>>a;
> 		nodes[i]=Node(i+1,a,k);
> 	}
> 	sort(nodes,nodes+n);//nlog(n)
> 	DC(0,n,0);
> 	cout<<"YES"<<endl;
> 	for(i=0;i<n;i++){
> 		cout<<tree[i][0]<<" "<<tree[i][1]<<" "<<tree[i][2]<<endl;
> 	}
> 	return 0;
> }

• Re:应该是超在..."//找到含有最小a的元素",想办法优化吧 (18) acedhu 2005-04-11 13:45:12