Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
谁能帮帮我,TLE了,思路就是建立一个排序二叉树,往里面添加节点,最后中序遍历得到答案。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator