题目分析

需将书籍从当前位置还原到原始位置，可通过两种操作：

• 操作1：书架内有空位时，书籍可左右移动。
• 操作2：取书并放到（同书架或其他书架的）空位上。 目标是最小化“操作2”的次数，或判断任务不可行。

算法思路

1. 并查集维护书架连通性

用**并查集（Union-Find）**维护书架的“连通关系”：若一本书当前在书架 ( i )，但原始位置在书架 ( j )，则将 ( i ) 和 ( j ) 合并为同一连通块。同一连通块内的书架可通过“空位 + 操作1”间接移动书籍，减少跨书架的“操作2”需求。

2. 最长递增子序列（LIS）优化单书架操作

对于单个书架，考虑“原本属于该书架且最终也应在该书架”的书。这类书可通过**操作1（书架内移动）**尽可能保留，减少“操作2”次数。

利用最长递增子序列（LIS），计算这类书中“能通过操作1保留的最大数量（LIS长度）”。则该书架需要的“操作2基础次数”为：( \text{这类书的总数} - \text{LIS长度} )。

3. 特殊情况处理

• 无空位且需移动：若所有书架都没有空位（初始无 0），但存在需要移动的书，则无法完成任务（输出 -1）。
• 连通块的空位需求：对于每个连通块，若块内没有空位，但存在需要移动的书，则必须额外执行一次“操作2”（取一本书创造空位，才能通过操作1移动其他书）。

算法标签

• 并查集（Union-Find）
• 最长递增子序列（LIS）
• 贪心思想

复杂度分析

• 时间复杂度：( O(nm \log m + n \alpha(n)) )。其中 ( \alpha ) 是阿克曼函数的反函数（并查集操作的均摊复杂度），( \log m ) 来自LIS的二分查找。
• 空间复杂度：( O(nm + \text{max(书编号)}) )，用于存储书的位置映射与辅助数组。

总结

本题通过并查集维护书架连通性，结合最长递增子序列优化单书架内的移动，最终通过贪心思想计算“操作2”的最小次数，并处理“无空位不可行”等特殊情况。