e316 - NOIP2017 2.图书管理员
題目描述
題目要求找出圖書館中，書籍編碼以特定需求碼結尾，且編碼最小的書籍。如果沒有符合條件的書籍，則輸出 -1。
解題思路
首先，將所有書籍的編碼進行排序。對於每個讀者的需求碼，計算出需求碼所代表的 10 的冪次方。然後，遍歷排序後的書籍編碼列表，使用模運算符 % 判斷書籍編碼是否以需求碼結尾。如果找到符合條件的書籍，立即輸出該書籍的編碼並結束搜尋。如果遍歷完所有書籍後仍未找到符合條件的書籍，則輸出 -1。
複雜度分析
- 時間複雜度: O(n log n + n * q)，其中 n 是書籍數量，q 是讀者數量。排序書籍編碼需要 O(n log n) 的時間，對於每個讀者，遍歷書籍編碼列表需要 O(n) 的時間。
- 空間複雜度: O(n)，用於儲存書籍編碼列表。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
using namespace std;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int n=read(),q=read(),b,c;
int a[n];
for(int i=0;i<n;++i)
a[i]=read();
sort(a,a+n);
while(q--){
b=read();
c=read();
int z=1;
bool ans=0;
while(b--)
z*=10;
for(int i=0;i<n;++i){
if(a[i]%z==c){
write(a[i]);
putchar_unlocked('\n');
ans=1;
break;
}
}
if(ans==0){
putchar_unlocked('-');
putchar_unlocked('1');
putchar_unlocked('\n');
}
}
}