「NOIP2017_Junior」图书管理员

题目

题目描述

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

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

格式

输入格式

第一行，包含两个正整数 n,q，以一个空格分开，分别代表图书馆里书的数量和读者的数量。

接下来的 n 行，每行包含一个正整数，代表图书馆里某本书的图书编码。

接下来的 q 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆 里读者的需求码的长度，第二个正整数代表读者的需求码。

输出格式

q 行，每行包含一个整数，如果存在第 i 个读者所需要的书，则在第 i 行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出−1。

样例

Input1

5 5 
2123 
1123 
23 
24 
24 
2 23 
3 123 
3 124 
2 12 
2 12

 Output1

23 
1123 
-1 
-1 
-1

思路

众所周知

   找最小&&没有被排序 一般是需要排序的

难点

   使用函数sort（）+cmp Or 自己选择一种排序方法

方法

1.sort+cmp

Sort是一个系统函数其内置算法是快速排序时间复杂度为 n*log2n

但它却是一个不稳定的的算法（后续可通过自定义函数改变这一现状）

int a[105];
cin>>a[1]>>a[2]>>a[3];
sort(a+1,a+4);
cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" ";

in:
4 7 2
out:
2 4 7

 可以看出sort默认是升序排列，而用自定义函数cmp可以做到降序排列。

bool cmp(int a,int b) {
    return a > b;
}
——————————————————————————main——————————————
int a[105];
cin>>a[1]>>a[2]>>a[3];
sort(a+1,a+4,cmp);
cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" ";

in:
4 7 2
out:
7 4 2

 Cmp不仅可以用在整型还可以用在字符串（string），字符（char），浮点数（double，float

），给构体等；

而本题适合用字符串来实现题目所要求的 && 不超时 && 简便；

2.本代码中使用的系统函数

string s;
cin>>s;
int l=s.size();
cout<<l;

in:
yijiansanlian
out:
13

.size()  用来计算字符串的长度；

string s;
cin>>s;
string l=s.substr(2,4);
cout<<l;

in:
yijiansanlian
out:
jian

s .substr(x,y)   用于计算字符串从第x+1个字符开始y个字符的子字符串；

代码

string book[1001];
bool cmp(string a, string b) {
    if (a.size() != b.size()) {
        return a.size() < b.size();
    }
    return a < b;
}
——————————————————main————————————————————————
	freopen("librarian.in","r",stdin);
	 freopen("librarian.out","w",stdout);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> book[i];
    }
    sort(book, book + n, cmp);
    for (int i = 0; i<=q-1; i++) {
        int len;
        string num;  
        cin >> len >> num;
        bool f = false;
        for (int j = 0; j<=n; j++){
            if (book[j].size() < len) {
                continue;
            } else {
                if (book[j].substr( book[j].size() - len, len) == num) {
                    cout << book[j] << endl;
                    f = true; 
                    break; 
                }
            }
        }
        if (f==0){
            cout << -1 << endl;
        }
    }
    return 0;
}