洛谷P3955图书管理员

liyucheng114514 · 2023-01-12 00:36:35 · 个人记录

题目传送门

• 题目类型：字符串的比较
• 题目算法：排序
• 题目要点：将图书编码读入并排序，以便快速知道最小的图书编码（"对于每一位读者，求出他所需要的书中图书编码最小的那本书，"）对上读者的需求码。如果对上，输出图书编码，否则输出-1

解题思路：

• 将表示图书编码的数组由小到大用sort进行排序，方便后续操作
• 但是由于如果把需求码全部读入再来边读入边找书会浪费空间，我们就采取对数字进行截断（取余）的方法处理，即取书的编号的后X位，仅需将该书编号%(10^需求码长度)，

• 循环查找，判断是否有对应的图书编码存在。

  • 是，输出图书编码
  • 否，cout<<"-1";break;←没有寻找到直接跳出本轮寻找

  代码：

  #include<algorithm>
  #include<iostream>
  #define N 10000
  using namespace std;
  long long f,q,n,a[N],x,y,g,ans[N];//n表示为图书馆的书，q表示为读者的数量
  long long p[114]={1,10,100,1000,10000,100000,1000000,10000000};//对于不同的需求码长度进行取余，上文提及
  int main()
  {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>q;
  for(int i=0;i<n;i++) cin>>a[i];//输入图书编码
  sort(a,a+n);//排序图书编码
  for(int i=0;i<q;i++)
  {
      f=0;//每当查找完一次需求码和图书编码后，标记重置为0
      cin>>x>>y;
      for(int j=0;j<n;j++)
      {
          g=a[j]%p[x];//上文有所提及的取余方式
          if(g==y)
          {
              cout<<a[j]<<endl;
              f=1;//查找到对应的图书编码后，标记为1
              break;//找到后直接跳出循环
          }
      }
      if(f==0) cout<<-1<<endl;//如果没有查找到（即g==y的判断内置语句块没有被执行），则按照题目输出-1
  }
  return 0;
  }