| ||||||||||
| 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