python/TangDou/AcWing_TiGao/T6/ErFen/113.md

##AcWing 113. 特殊排序

前导知识

一、题目描述

有 N 个元素，编号 1,2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但 不具有传递性。

注意：不存在两个元素大小相等的情况。

也就是说，元素的大小关系是 N 个点与 \frac{N×(N−1)}{2} 条有向边构成的 任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 10000 次提问来获取信息，每次提问只能了解某两个元素之间的关系。

现在请你把这 N 个元素排成一行，使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。

例如，编号为 a 和 b 的两个元素，如果元素 a 小于元素 b，则 compare(a,b) 返回 true，否则返回 false。

将 N 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

数据范围 1≤N≤1000

输入样例 [[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例 [3, 1, 2]

二、理解

本题与一般排序有三个区别：

• 交互式，你并不知道大小关系，只能通过调用compare接口询问；
• 大小不具备传递性，比如a < b,b < c 并不能推出a < c；
• 不能超过一万次询问，数据范围为1000，nlogn=1000*9,略小于一万

对于其第二个性质仅仅导致答案不唯一，题目仅要求输出一种答案，所以可以忽视该条件。因为它会有Special\ Judge嘛。

采用 二分插入排序 解决该问题:

• 本题中不体现对值的使用，因为隐藏的compare中才会有这个 值 的概念，我们不关心,我们只关心序号
• 将第一个元素序号压入向量里，然后枚举后续的每一个序号，二分查找合适的位置r

五、实现代码

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> a; // 结果数组
        // a数组中入的是序号，没有值，本题我们在代码中不关注值，值是在我们黑盒的compare中体现的
        a.push_back(1); // 第一个元素序号入数组

        for (int k = 2; k <= N; k++) { // 枚举2~N个元素,它要放在哪里？
            int l = 0, r = k - 1;      // 右边界位置,左闭右开
            while (l < r) {
                int mid = (l + r) >> 1;
                // 如果元素a小于元素b，则 compare(a,b) 返回 true
                if (compare(k, a[mid])) // a[mid]是指序号
                    r = mid;
                else
                    l = mid + 1;
            }
            a.insert(a.begin() + l, k);
        }
        return a;
    }
};