题目分析

这是一个排列构造问题，需要构造一个总指挥的排列，满足所有相邻约束：

• 对于任意相邻的 i 和 j（假设 i < j）
• i 不能严格位于 j 排名的后半部分

关键点："严格位于后半部分"意味着排名位置 pos ≥ ceil(j/2)

算法思路

核心思想

使用贪心插入算法：

1. 按编号递增顺序处理：从总指挥0开始，依次处理1,2,...,N-1
2. 维护当前排列：始终保持已处理的指挥满足所有约束
3. 尝试所有插入位置：为新指挥寻找合适的插入位置

关键观察

• 当处理总指挥 i 时，所有已在排列中的指挥编号都小于 i
• 因此所有新创建的相邻关系都是 (x, i) 形式，其中 x < i
• 只需要检查 pos[i][x] < (i+1)/2 是否成立

代码详解

数据结构

vector<vector<int>> pos(N);  // pos[i][j] 表示在总指挥i的排名中，指挥j的位置

• pos[i] 是一个长度为 i 的向量
• pos[i][j] = r 表示在指挥i的排名中，指挥j排在第r位（0表示最好）

输入处理

for (int i = 1; i < N; i++) {
    pos[i].resize(i, -1);
    for (int r = 0; r < i; r++) {
        int p;
        cin >> p;
        pos[i][p] = r;  // 记录位置
    }
}

贪心构造算法

vector<int> ordering;
ordering.push_back(0);  // 从总指挥0开始

for (int i = 1; i < N; i++) {
    bool inserted = false;
    int allowedThreshold = (i + 1) / 2;  // 允许的最大排名位置
    
    // 尝试所有可能的插入位置（包括两端）
    for (int posIns = 0; posIns <= (int)ordering.size(); posIns++) {
        bool canInsert = true;
        
        // 检查左邻居
        if (posIns > 0) {
            int leftNeighbor = ordering[posIns - 1];
            // 检查条件：leftNeighbor在i的排名中的位置
            if (pos[i][leftNeighbor] >= allowedThreshold) {
                canInsert = false;
            }
        }
        
        // 检查右邻居
        if (posIns < (int)ordering.size()) {
            int rightNeighbor = ordering[posIns];
            if (pos[i][rightNeighbor] >= allowedThreshold) {
                canInsert = false;
            }
        }
        
        // 如果这个位置可行，插入并退出循环
        if (canInsert) {
            ordering.insert(ordering.begin() + posIns, i);
            inserted = true;
            break;
        }
    }
    
    // 理论上总是能找到插入位置
    if (!inserted) {
        ordering.push_back(i);  // 后备方案
    }
}

算法原理

正确性证明

归纳法证明：

1. 基础情况：只有总指挥0时，排列有效
2. 归纳假设：假设处理前k个指挥的排列满足所有约束
3. 归纳步骤：处理第k+1个指挥时
   • 对于每个可能的插入位置，检查新创建的相邻关系
   • 条件 pos[i][neighbor] < (i+1)/2 确保不违反约束
   • 由于问题保证有解，总能找到合适位置

为什么这样能保证找到解？

• 算法尝试所有可能的插入位置（包括排列两端）
• 对于每个位置，检查所有新创建的相邻关系
• 由于题目保证解存在，至少有一个位置满足条件

复杂度分析

时间复杂度

• 外层循环：O(N)，处理每个总指挥
• 内层循环：O(N)，尝试所有插入位置
• 位置检查：O(1)，常数时间检查
• 总复杂度：O(N²)，对于 N ≤ 1000 可接受

空间复杂度

• pos 数组：O(N²) 存储排名信息
• ordering 向量：O(N) 存储当前排列

样例分析

样例1

输入：

6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

算法执行过程：

1. 初始：[0]
2. 插入1：检查位置 → [1, 0]
3. 插入2：检查位置 → [2, 1, 0]
4. 插入3：检查位置 → [3, 2, 1, 0]
5. 插入4：检查位置 → [4, 3, 2, 1, 0]
6. 插入5：检查位置 → [4, 2, 5, 3, 1, 0]

最终输出：4 2 5 3 1 0

算法优势

1. 实现简单：代码简洁，逻辑清晰
2. 正确性保证：通过检查所有可能位置确保找到解
3. 效率足够：O(N²) 复杂度满足题目限制
4. 通用性强：不依赖特殊排名模式

关键技巧

1. 提前计算位置：将排名转换为位置索引，方便快速查询
2. 允许阈值计算：(i+1)/2 正确处理奇偶情况
3. 全面尝试：尝试所有可能的插入位置，不依赖启发式规则
4. 归纳构造：逐步构建，保持每一步都满足约束