题解 P3955 【图书管理员】

2018-09-15 14:32:02


看下面的人都是字符串啊,模拟啊,真是不给数据结构留点后路。

这道题我是用树写的。

把编码每一位反向插入树中,查找时编码反向查询就行了。

#include <iostream>
#include <cstdio>
using namespace std;
struct xtree{//建树
       xtree *sons[20];//下一位数字
       int cou;
       int nums;//最小的编码
};
xtree *neww(){//新建一个新节点
      xtree *p=new xtree;
      p->cou=0;
      for(int i=0;i<10;i++)
         p->sons[i]=NULL;
      return p;
}
void hui(xtree *now,int num,int xsxs){//递归插入书籍信息
     if(num==0){//最底层
       now->cou++;
       if(now->nums!=0)
         now->nums=min(now->nums,xsxs);
       else
         now->nums=xsxs;
       return;
     }
     //否则继续递归
     if(now->sons[num%10]==NULL)
       now->sons[num%10]=neww();
     hui(now->sons[num%10],num/10,xsxs);
     if(now->nums!=0)
       now->nums=min(now->nums,xsxs);
     else
       now->nums=xsxs;
}
int aq(xtree *now,int num){//询问
    if(now==NULL)
      return -1;
    if(num!=0)
      return aq(now->sons[num%10],num/10);
    return now->nums;
}
int main(){
    xtree *root=neww();//根节点
    int n,q,junk;
    cin>>n>>q;
    for(int i=0;i<n;i++){
       scanf("%d",&junk);
       hui(root,junk,junk);//插入
    }
    for(int i=0;i<q;i++){
       int wei;
       scanf("%d%d",&wei,&junk);
       printf("%d\n",aq(root,junk));//寻找
    }
    return 0;
}