图书管理员题解

图书管理员

https://ac.nowcoder.com/acm/problem/16422

题目描述

链接：https://ac.nowcoder.com/acm/problem/16422
来源：牛客网

图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。

每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。

小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。

输出样例：
23
1123
-1
-1
-1

总结思想

本题其实只是单纯利用了排序进行比较，从时间复杂度上来看快速排序效率最高为log(n)但是我这里偷懒利用STL里的sort()排序，其实在简单的元素sort排序仅次于快排，这里是可以ac的。
整体思想是定义结构体，在结构体里定义两个整型元素len，num分别表示输入的数字长度和书目序号，并声明一个全局的结构体数组，这里有条件：
对于 100%的数据，1≤n ≤1,000，1 ≤ q ≤ 1,000，所有的图书编码和需求码均不超过 10,000,000。
这个数并不是很大，可见本题并不想在储存空间上难为我们，所以本题更简单了我直接定义了数组长度为1000+7；这里加7是为数组预留出更大的空间防止越界！
下面就是定义数组存放已经存在的书目编号并输入，此时先对我们输进去编号进行sort排序，我们都知道sort排序默认是由小到大。最核心的思想就是因为我们要的是找后几位数，于是我们不难想出用排好序的存在的书目编号减去读者想要的编号只要结果大于等于0并且对我们事先在结构体里对应编号的长度与10^q取余如果结果为0就将其存入结果数组中，这就是最小结果，定义一个bool类型的变量，如果找到对应的编号书籍就变为true然后break，执行下一读者的编号查找，如果没找到就将-1存入结果数组当中，最后输出即可。

代码参考

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<math.h>
using namespace std;

struct CodeBook
{
    int len;
    int num;
}codebooks[1000+7];

int main()
{
    int repertory[1000 + 7], result[1000 + 7];
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &repertory[i - 1]);
    }
    sort(repertory, repertory + n);
    for (int j = 1; j <= q; j++)
    {
        scanf("%d%d", &codebooks[j - 1].len, &codebooks[j - 1].num);
        bool flag = false;
        for (int i = 1; i <= n; i++)
        {
            int res = repertory[i - 1] - codebooks[j - 1].num;
            if (res >= 0 && res % (int)pow(10, codebooks[j - 1].len) == 0)
            {
                result[j - 1] = repertory[i - 1];
                flag = true;
                break;
            }
        }
        if (flag==false)
        {
            result[j - 1] = -1;
        }
    }
    for (int k = 1; k <= q; k++)
    {
        printf("%d\n", result[k - 1]);
    }
}

希望可以帮助到你们加油！