#3693. 图书分类
图书分类
题目描述
图书馆里有 n 本待分类的书,每本书记录着它的代号 pi。图书馆共有 m 个书架,每个书架上已经有一些书,并在对应的位置上刻下了这个书架应有的书的代号 ai。
输入格式
输入的第一行含两个整数 n和 m (1 ≤ n, m ≤ 1000),接下来的 n 个整数是每本书的代号 pi (1 ≤ pi ≤ 1000), 接下来的 m 个整数是书架的代号 ai (1 ≤ ai ≤ 1000)。每个代号都是在 1 到 1000 之间的整数。
输出格式
输出 n 行,第 i 行输出第 i 本书应该被分到的书架编号 j。如果没有有效的书架能完成分类,输出 -1。如果有多解,输出其中的任何一个。
样例
3 2
1 2 3
1 2
-1
4 3
1 2 3 1
1 2 3
1
2
3
1
说明/提示
如果某本应被放在 j 号书架上的书 p 也出现在 j 号书架上,那么它会被认为是正确分类的。否则,正确的分类是当 p 是第一次出现在 j 号书架上的书,而之前所有的书架上都没有 p 出现过。
解析
题解
解题思路
这道题目的意思是,对于每本书,我们需要找到一个书架,使得这本书的代号在该书架上存在的情况有两种:
- 这本书已经存在于该书架上了,那么这个书架就是它的正确归宿。
- 如果这本书在任何书架上都没有出现过,那么可以选择任何一个还未来过这本书的书架,但一旦选择,以后其他书如果也是这个名字,就必须放在同一个书架上了。
我们的目标是为每本书找到正确的书架,否则输出-1。
算法选择理由
这道题的核心是要管理每个书架上的书,同时确保当一本书的代号在多个书架上时,正确处理。使用哈希集合来跟踪每个书架上的书是一个好方法。此外,我们需要跟踪书架是否已经被用来存放某本书,但只有在没有冲突的情况下。
复杂度分析
对于每本书,我们都要检查所有的书架。在最坏情况下,每个书的检查时间是O(m)。由于n和m都最大为1000,所以总的时间复杂度是O(n*m)=1e6,这在1s内是可以接受的。
代码解释
- 读取输入的书籍和书架的代号。
- 使用一个布尔数组
used来跟踪书架是否已经被使用过(即是否有其他书被放在了这里,并且该书架的书没有与其他书冲突)。 - 对于每本书,我们检查每个书架,看看是否已经有这本书了。如果有,就放在那个书架上。
- 如果没有找到现有的书架,那么我们就找一个
used为假的书架。在选择这个书架之前,我们需要确保在这之前没有其他书架上有这本书。 - 一旦选择了书架,就更新该书架的集合,并记录下来。
通过这种方式,我们可以有效地分配每本书到正确的书架上。如果在任何时候没有找到合适的书架,就输出-1。
来源
AI 生成 · olympiccoder:7b · 普及 · 贪心