Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

谁能帮帮我,TLE了,思路就是建立一个排序二叉树,往里面添加节点,最后中序遍历得到答案。

Posted by zhb_msqx at 2007-09-09 19:30:55 on Problem 3374
#include <iostream>
#include <fstream>
using namespace std;

#define INF 1000000


int n,c;

struct node{
	int uc,dc;  //分别代表分子,分母
	node *left,*right;
	node(){
		uc=0;dc=0;
		left=NULL;right=NULL;
	}
};

node ans[INF];
int an;

struct tree{
	int tn;
	node *root;
	node *cur;
	tree(){
		tn=0;
		cur=new node();
	}
	void add(node *tmp);
	void dfs(node *tmp);

} t;

void tree::add(node *tmp){
	if(root==NULL){
		root=tmp;
		tn++;
	}else{
		cur=root;
		bool equal=false;
		while(!equal){
			int gs=tmp->dc*cur->uc-tmp->uc*cur->dc;
			if(gs<0){
				if(cur->right==NULL){
					cur->right=tmp;
					tn++;
					return;
				}
				cur=cur->right;
			}else if(gs>0){
				if(cur->left==NULL){
					cur->left=tmp;
					tn++;
					return;
				}
				cur=cur->left;
			}else{
				equal=true;
				return;
			}

		}
	}
}

void tree::dfs(node *tmp){
	cur=tmp;
	if(tmp!=NULL){
		dfs(tmp->left);
		ans[an++]=*tmp;
		dfs(tmp->right);
	}
}

void init(){
	an=0;
	int i,j,k;
	for(i=1;i<=n;i++){
		for(j=0;j<=i;j++){

			node *newp=new node();
			newp->uc=j;newp->dc=i;
			t.add(newp);

		}

	}
	t.dfs(t.root);
/*	for(i=0;i<an;i++){
		cout<<ans[i].uc<<" "<<ans[i].dc<<endl;
	}
	cout<<endl;
*/
}

void main(){
	ifstream cin("data.txt");
	int i,j,k;

	cin>>n>>c;
	init();
//	cout<<t.tn<<endl;
	for(i=0;i<c;i++){
		cin>>j;
		if(j>an){
			cout<<"No Solution"<<endl;
			continue;
		}
		cout<<ans[j-1].uc<<"/"<<ans[j-1].dc<<endl;
	}

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator