图书管理员

题目描述

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

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

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

分析

对输入的图书号进行排序，等待输入查询码时，从小到大依次匹配图书号的结尾，如果能匹配上就输出并进行下一次查询，不能则输出-1。

代码

#include <iostream>
using namespace std;

const int MAXN = 1001;

int books[MAXN]; // 存储图书编码

void mswap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void q_sort(int l, int r) { // 快排
    int mid = books[(l + r) / 2];
    int i = l;
    int j = r;
    do {
        while (books[i] < mid)
            i++;
        while (books[j] > mid)
            j--;
        if (i <= j) {
            mswap(books[i], books[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j)
        q_sort(l, j);
    if (i < r)
        q_sort(i, r);
}

bool is_end(int a, int b) { // 判断b是否为a的后缀
    while (b) { // 当b还有个位
        if ((a % 10) - (b % 10)) { // 取a和b的个位进行比较
            return false;
        }
        a /= 10; // a去掉个位
        b /= 10; // b去掉个位
    }
    return true;
}

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> books[i];
    }
    q_sort(0, n - 1);
    for (int i = 0; i < q; i++) {
        int len; // 我也不知道有啥用
        int end;
        cin >> len >> end;
        int ans = -1; // 没找到就输出-1
        for (int j = 0; j < n; j++) { // 从小到大和图书编码匹配
            if (is_end(books[j], end)) { // 判断匹配
                ans = books[j];
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}