题目描述
图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。
每位借书的读者手中有一个需求码,这个需求码也是一个正整数。
如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他需要的书,请输出 −1。
样例
输入
5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2 12
输出
23
1123
-1
-1
-1
算法1
贪心枚举
编号和需求码均用整数表示。因为要输出最小的图书编号,将所有图书编号从小到大排序。
同时,事先打表准备一个10、100、1000、…、10000000的数组,用来进行取余运算。
从小到大将图书编号对位数对应的底,如位数为3,则图书编号对1000取余,若余数刚好就是需求码,直接输出该图书编号,即为所求。否则,输出-1。
时间复杂度
O(nlogn)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1009;
ll n; // 图书数量
ll q; // 读者数量
ll book[N]; // 图书编号
ll base[10] = {0, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 10000000, 100000000};
void input() {
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> book[i];
sort(book, book+n);
}
ll solve() {
int len, code; // 长度、需求码
while (q--) {
cin >> len >> code;
bool found = false;
for (int i = 0; i < n; i++) {
if (code == book[i] % base[len]) {
cout << book[i] << endl;
found = true;
break;
}
}
if (!found) {
cout << -1 << endl;
}
}
}
int main() {
input();
solve();
return 0;
}