全是RE,用的指针
查看原帖
全是RE,用的指针
540509
KGB_Stalin楼主2021/11/18 14:16

用的指针,全都RE了本地与样例都过了

//Created by Kaiser_cat;
#include<bits/stdc++.h>
using namespace std;

const int INF=0x7fffffff;
typedef struct twofindtree{
    int key;
    int size=0;
    int num=0;
    struct twofindtree *parent,*Left,*Right;
}Link;

Link *root;

void insertnode(int k){
    Link *now,*it;
    it=root;
    now=(Link*) malloc(sizeof (Link));
    now->size=1;
    now->num=1;
    now->key=k;
    while (1){
        it->size++;
        if(k>it->key){
            if(it->Right!=NULL){
                it=it->Right;
                continue;
            } else{
                it->Right=now;
                now->parent=it;
                break;
            }
        } else if(k<it->key){
            if(it->Left!=NULL){
                it=it->Left;
                continue;
            } else{
                it->Left=now;
                now->parent=it;
                break;
            }
        } else if(k==it->key){
            it->num++;
            free(now);
            return;
        }
    }
    now->Right=NULL;
    now->Left=NULL;
}
void Begining(int k){
    root=(Link*) malloc(sizeof (Link));
    root->key=k;
    root->size=1;
    root->num=1;
    root->parent=NULL;
    root->Left=NULL;
    root->Right=NULL;
}
void qianqufind(int k){
    Link *it=root;
    int min;
    min=root->key;
    while (1){
        if(it==NULL){
            cout<<"-2147483647"<<endl;
            return;
        }
        if(k==it->key){
            if(it->Left!=NULL){
                Link *end=it->Left;
                while (1){
                    if(end->Right==NULL){
                        break;
                    }
                    end=end->Right;
                }
                min=end->key;
                printf("%d\n",min);
                return;
            } else{
                if(min<it->key){
                    printf("%d\n",min);
                    return;
                } else{
                    cout<<"-2147483647"<<endl;
                    return;
                }
            }
        } else if(k<=it->key){
            it=it->Left;
        } else if(k>it->key){
            min=it->key;
            it=it->Right;
        }
    }
}
void houqufind(int k){
    Link *it=root;
    int max;
    max=root->key;
    while (1){
        if(it==NULL){
            printf("2147483647\n");
            return;
        }
        if(k==it->key){
            if(it->Right!=NULL){
                Link *end=it->Right;
                while (1){
                    if(end->Left==NULL){
                        break;
                    }
                    end=end->Left;
                }
                max=end->key;
                printf("%d\n",max);
                return;
            } else{
                if(max>it->key){
                    printf("%d\n",max);
                    return;
                } else{
                    printf("2147483647\n");
                    return;
                }
            }
        } else if(k<=it->key){
            max=it->key;
            it=it->Left;
        } else if(k>it->key){
            it=it->Right;
        }
    }
}
void xfind(int k){
    Link *it=root;
    int order;
    while (1){
        if(root==NULL){
            break;
        }
        if(k==it->key){
            if(it->Left==NULL){
                order+=0;
            } else{
                order+=it->Left->size;
            }
            break;
        } else if(k<it->key){
            it=it->Left;
            continue;
        } else if(k>it->key){
            if(it->Left==NULL){
                order+=it->num;
            } else{
                order+=it->num+it->Left->size;
            }
            it=it->Right;
            continue;
        }
    }
    printf("%d\n",order+1);
}
void findx(int k){
    Link *it=root;
    int number;
    while (1){
        if(it==NULL){
            number=INF;
            break;
        }
        if(it->Left!=NULL){
            if(it->Left->size>=k){
                it=it->Left;
                continue;
            } else if(it->Left->size+it->num>=k){
                number=it->key;
                break;
            } else{
                k=k-it->Left->size-it->num;
                it=it->Right;
                continue;
            }
        } else {
            if(it->num>=k){
                number=it->key;
                break;
            } else{
                k=k-it->num;
                it=it->Right;
                continue;
            }
        }
    }
    printf("%d\n",number);
}


int main(){
    int n,a,b,flag=1;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>a>>b;
        if(a==1){
            xfind(b);
        } else if(a==2){
            findx(b);
        }else if(a==3){
            qianqufind(b);
        }else if(a==4){
            houqufind(b);
        }else if(a==5){
            if(flag==1){
                Begining(b);
                flag=0;
                continue;
            }
            insertnode(b);
        }
    }
    return 0;
}
2021/11/18 14:16
加载中...