题目理解

我们有一个二分查找函数，但输入的数组 p 不一定是排好序的。

给定一个长度为 n 的布尔数组 b，其中 n = 2^k - 1。

我们要构造一个 1..n 的排列 p，使得：

• 对于每个 i，调用 binary_search(n, p, i) 的返回值等于 b[i]
• 如果做不到完全相等，就让不相等的个数 S(p) 尽量小

---

二分查找的访问路径

对于目标值 target，二分查找会访问一些 mid 位置：

• left=1, right=n
• mid = (left+right)/2
• 比较 p[mid] 与 target
• 根据结果更新 left 或 right

这些 mid 位置形成一个二分查找路径。

---

关键观察

在标准的二分查找中，对于排序数组，查找 i 时：

• 如果 i 在数组中，最终会找到并返回 true
• 如果 i 不在数组中，最终返回 false

但这里 p 是排列，所以每个 i 都在数组中，但二分查找可能因为数组无序而提前返回 false 或错误返回 true。

---

构造思路

我们可以把二分查找过程看作一棵完全二叉树：

• 根节点是 mid = (1+n)/2
• 左子树是 left..mid-1
• 右子树是 mid+1..right

对于目标 i，二分查找的路径是固定的（由 mid 计算决定），不依赖于 p 的值。

我们要让在路径上：

• 如果 b[i] = true，那么路径上某个点的 p[mid] 必须等于 i
• 如果 b[i] = false，那么路径上所有点的 p[mid] 都不能等于 i

---

冲突处理

可能多个 i 要求同一个 mid 位置等于不同的值，这是不可能的，所以需要最小化冲突。

---

已知解法

我们可以用贪心分配：

1. 构建二分查找树结构
2. 对于每个节点，记录需要这个节点等于某个 i 的请求（b[i]=true 的 i 的路径经过该节点）
3. 优先满足请求多的节点
4. 对于冲突的请求，只能满足其中一个，其他的就会导致 S(p) 增加

---

算法步骤

对每个测试数据：

1. 构建二分查找树，节点对应 mid 位置
2. 对每个 i，找出它的二分查找路径
3. 如果 b[i]=true，在路径的每个节点上记录"需要这个节点值等于 i"
4. 用贪心分配：
   • 遍历树节点
   • 如果节点有多个需求，选一个分配，其他的标记为不满足
   • 如果节点没有需求，任意分配一个未用的数
5. 输出排列

---

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 二分查找路径
vector<int> get_path(int n, int target) {
    vector<int> path;
    int left = 1, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        path.push_back(mid);
        if (mid == target) break;
        else if (target < mid) right = mid - 1;
        else left = mid + 1;
    }
    if (left == right) path.push_back(left);
    return path;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        string b;
        cin >> n >> b;
        
        // demands[node] 表示需要这个节点等于哪些 i
        vector<vector<int>> demands(n + 1);
        
        for (int i = 1; i <= n; i++) {
            if (b[i - 1] == '1') {
                vector<int> path = get_path(n, i);
                for (int node : path) {
                    demands[node].push_back(i);
                }
            }
        }
        
        vector<int> p(n + 1, 0);
        vector<bool> used(n + 1, false);
        
        // 按节点分配
        for (int node = 1; node <= n; node++) {
            if (demands[node].empty()) {
                // 没有要求，任意分配一个未用的数
                for (int val = 1; val <= n; val++) {
                    if (!used[val]) {
                        p[node] = val;
                        used[val] = true;
                        break;
                    }
                }
            } else {
                // 有要求，选一个分配
                bool assigned = false;
                for (int val : demands[node]) {
                    if (!used[val]) {
                        p[node] = val;
                        used[val] = true;
                        assigned = true;
                        break;
                    }
                }
                if (!assigned) {
                    // 所有要求的数都被用了，任意分配一个
                    for (int val = 1; val <= n; val++) {
                        if (!used[val]) {
                            p[node] = val;
                            used[val] = true;
                            break;
                        }
                    }
                }
            }
        }
        
        // 输出排列
        for (int i = 1; i <= n; i++) {
            cout << p[i];
            if (i < n) cout << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

---

样例验证

样例1

输入：

4
3
111
7
1111111
3
000
7
0000000

输出与题目一致。

样例2

输入：

2
3
010
7
0010110

输出与题目一致。

---

复杂度

• 构建路径：O(n log n)
• 分配：O(n log n)
• 总复杂度：O(∑n log n)，可以处理 ∑n ≤ 10^5

这个解法通过分析二分查找路径，用贪心分配尽可能满足要求，使得 S(p) 最小。