先说一个问题：开始我只开到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的元素",想办法优化吧 (1434) ArXoR 2005-04-06 22:49:31
  • Re:应该是超在..."//找到含有最小a的元素",想办法优化吧 (18) acedhu 2005-04-11 13:45:12