「JOI Open 2024」图书馆 3 题解

题目大意

有一个长度为$N$的书架，每个位置放一本书。正确的排列方式是一个未知的排列$B_0, B_1, \cdots, B_{N-1}$。我们可以通过一个特殊机器进行查询：给定一个排列$a$，机器返回从$a$恢复到正确排列$B$所需的最小操作次数。

恢复操作的定义是：每次找到最左边位置错误的书$x$，将其与它正确位置上当前的书$y$交换。

我们需要在最多$5000$次查询内确定正确的排列$B$。

算法思路

核心观察

本题的关键在于理解查询返回值与排列之间的关系。通过分析交换过程，我们可以发现：

每次查询返回的操作次数实际上等于排列的逆序对的一种特殊计数，与正确排列$B$相关。

逐步构建策略

我们从左到右逐个确定每个位置上的正确书籍：

1. 初始化：从排列$[0, 1, 2, \cdots, N-1]$开始
2. 对于每个位置$i$（从$1$到$N-1$）：
   • 使用二分查找确定当前书应该插入到前面已排序部分的哪个位置
   • 通过查询不同插入位置对应的操作次数来推断正确位置

代码实现详解

#include "library3.h"
#include <bits/stdc++.h>
using namespace std;

void solve(int n) {
    vector<int> b(n);
    
    // 初始化：假设当前排列为[0, 1, 2, ..., n-1]
    for (int i = 0; i < n; ++i)
        b[i] = i;

    // 从第1个位置开始（索引从0开始），逐个确定正确位置
    for (int i = 1; i < n; ++i) {
        int now = query(b);  // 查询当前排列的操作次数
        
        // 二分查找：确定b[i]应该插入到前面已排序部分的哪个位置
        auto check = [&](int mid)->bool {
            // 临时构造一个新排列：将b[i]插入到位置mid
            int tmp = b[i];
            b[i] = b[mid];
            
            // 将[mid, i-1]区间的书向右移动一位
            for (int j = mid; j >= 1; --j)
                b[j] = b[j - 1];
            
            b[0] = tmp;  // 临时处理
            
            // 查询新排列的操作次数
            int tt = query(b);
            
            // 恢复原排列
            for (int j = 0; j < mid; ++j)
                b[j] = b[j + 1];
            
            b[mid] = b[i];
            b[i] = tmp;
            
            // 关键判断：如果操作次数减少，说明插入位置正确
            return tt < now + mid + 1;
        };
        
        int l = 0, r = i - 1, ans = -1;
        
        // 二分查找正确的插入位置
        while (l <= r) {
            int mid = l + r >> 1;  // 中间位置
            
            if (check(mid))
                r = mid - 1, ans = mid;  // 可以更靠左
            else
                l = mid + 1;  // 需要更靠右
        }
        
        // 如果找到了正确位置，进行交换
        if (ans != -1)
            swap(b[i], b[ans]);
    }
    
    // 输出最终确定的正确排列
    answer(b);
}

关键技巧分析

1. 二分查找的运用

• 对于每个位置$i$，我们在$[0, i-1]$范围内二分查找正确插入位置
• 通过比较查询结果的变化来判断位置是否正确

2. 排列构造与恢复

• check函数临时构造测试排列，查询后立即恢复原状
• 避免了对原始排列的破坏，保证后续查询的正确性

3. 查询次数控制

• 每个位置最多进行$\log N$次查询
• 总查询次数为$O(N \log N)$，对于$N \leq 500$完全满足$5000$次限制

复杂度分析

• 时间复杂度：$O(N^2 \log N)$（每次查询需要$O(N)$时间构造排列）
• 空间复杂度：$O(N)$
• 查询次数：$O(N \log N)$，在$N=500$时约为$500 \times 9 = 4500$次

算法正确性

该算法基于以下重要观察：当我们将一本书插入到正确位置时，总的操作次数会显著减少。通过二分查找，我们能够高效地定位这个正确位置。

总结

本题展示了一种巧妙的交互题解法：

• 利用问题的特殊性质（操作次数的单调性）
• 结合二分查找减少查询次数
• 通过临时构造和恢复排列来收集信息

这种"逐步构建+二分验证"的思路在很多交互题中都有应用，是解决此类问题的有效范式。