题解 P3955 【图书管理员】
聪明的猪
2019-09-22 11:46:28
~~蒟蒻题解，dalao轻喷~~
# 整体思路
其实这道题还算比较简单（~~去你的~~），我们将其全部输入之后再一个一个处理，对比编码和需求码后将最小的分别对应地储存，时间复杂度大概为 $ \mathcal{O}\left( n^2 \right) $ 吧~~主要是我太蒻了~~。
# 核心代码详解
气势磅礴的头文件。
```cpp
#include <algorithm> // std::min
#include <array> // std::array
#include <cmath> // std::pow
#include <iostream> // std::cin，std::cout，std::endl
#include <limits> // std::numeric_limits
#include <memory> // std::shared_ptr
```
用来储存需求码的结构体。
```cpp
struct request
{
bool flag; // 标记是否找到了对应的图书编码
int len; // 需求码长度
long code, min; // 需求码和当前对应最小的图书编码
};
```
来一波数组。
```cpp
std::array<long, 1010> bookCode; // 图书编码
std::array<std::shared_ptr<request>, 1010> requestCode; // 需求码
```
以下缩进皆为main函数内。
气势磅礴的初始化。
```cpp
for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.end(); iter++) // 使用了迭代器，其实没有什么卵用
{
*iter = std::make_shared<request>();
(*iter)->len = 0;
(*iter)->code = 0;
(*iter)->min = (std::numeric_limits<long>::max)() - 1; // 将min设置为long的最大值
(*iter)->flag = false;
}
```
气势磅礴的输入。
```cpp
std::cin >> n >> q;
for (std::array<long, 1010>::iterator iter = bookCode.begin(); iter != bookCode.begin() + n; iter++) // 然并卵
{
std::cin >> *iter;
}
for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.begin() + q; iter++) // 然并卵
{
std::cin >> (*iter)->len >> (*iter)->code;
}
```
真正的核心代码。
```cpp
for (int i = 0; i < q; i++) // 需求码循环
{
for (int j = 0; j < n; j++) // 图书编码循环
{
if (bookCode.at(j) % static_cast<long>(std::pow(10, requestCode.at(i)->len)) == requestCode.at(i)->code) // 判断是否是需要的图书
{
requestCode.at(i)->min = std::min(bookCode.at(j), requestCode.at(i)->min); // 选最小
requestCode.at(i)->flag = true; // 设为已有编码了
}
}
}
```
# 整体代码
拒绝抄袭，共创和谐洛谷
```cpp
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <limits>
#include <memory>
struct request
{
bool flag;
int len;
long code, min;
};
std::array<long, 1010> bookCode;
std::array<std::shared_ptr<request>, 1010> requestCode;
int main(void)
{
int n = 0, q = 0;
bookCode.fill(0);
for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.end(); iter++)
{
*iter = std::make_shared<request>();
(*iter)->len = 0;
(*iter)->code = 0;
(*iter)->min = (std::numeric_limits<long>::max)() - 1;
(*iter)->flag = false;
}
std::cin >> n >> q;
for (std::array<long, 1010>::iterator iter = bookCode.begin(); iter != bookCode.begin() + n; iter++)
{
std::cin >> *iter;
}
for (std::array<std::shared_ptr<request>, 1010>::iterator iter = requestCode.begin(); iter != requestCode.begin() + q; iter++)
{
std::cin >> (*iter)->len >> (*iter)->code;
}
for (int i = 0; i < q; i++)
{
for (int j = 0; j < n; j++)
{
if (bookCode.at(j) % static_cast<long>(std::pow(10, requestCode.at(i)->len)) == requestCode.at(i)->code)
{
requestCode.at(i)->min = std::min(bookCode.at(j), requestCode.at(i)->min);
requestCode.at(i)->flag = true;
}
}
}
for (int i = 0; i < q; i++)
{
if (!(requestCode.at(i)->flag))
{
std::cout << -1 << std::endl;
}
else
{
std::cout << requestCode.at(i)->min << std::endl;
}
}
return 0;
}
```
~~A了这道题，祝你们成功~~