题目描述
图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。
每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。
小 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; }