AcWing113.特殊排序

题目

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

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

也就是说，元素的大小关系是 $N$ 个点与 $N\ast (N-1)/2$ 条有向边构成的任意有向图。

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

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

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

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

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

数据范围

$1\le N\le 1000$

输入样例

[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例

[3, 1, 2]

分析

根据数学归纳法，假设前 $k-1$ 个元素已经按要求排成一行，如果能确定第 $k$ 个元素应该放在哪一个前面，即可解决此问题。

可以通过这样一种二分法确定第 $k$ 个元素的位置：若第 $k$ 个元素比第 $mid$ 个元素小，令 $r=mid$，否则令 $l=mid+1$。二分的初始区间可设为 $[1,k]$，区间中的 $k$ 这个值表示放在所有 $k-1$ 个元素之后。

可以证明二分一定可以找到一个合法的位置插入，证明如下。

1. 如果第 $k$ 个元素比第 $mid$ 个元素小。
   继续比较 $k$ 与 $mid-1$ 这两个元素，若第 $k$ 个元素比第 $mid-1$ 个元素大，则 $k$ 可以插在 $mid-1$ 与 $mid$ 之间；否则说明元素 $k$ 比元素 $mid-1$ 小，那就再比较 $k$ 与 $mid-2$ 这两个元素，依此类推，直到发现第 $k$ 个元素比第 1 个元素小，那就放在最前边。
2. 如果第 $k$ 个元素比第 $mid$ 个元素大，同理。

以上只是一个证明，当然不会真的去依次比较 $k$ 与每个元素。实际上通过二分，每询问一次 （$k$ 与 $mid$），就可以把区间 $[l,r]$ 缩小一半，因此至多 $logk$ 次询问就可以确定 $k$ 应该放在哪里。把 $N$ 个元素排成一行的总询问次数不超过 $NlogN$。

代码

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.class Solution {
private:vector<int> arr;//第一个比arr[k]大的数的位置int binarySearch(int k) {int left = 0;int right = k;while (left < right) {int mid = (left + right) >> 1;if (compare(arr[k], arr[mid])) { //arr[k] < arr[mid]right = mid;} else {left = mid + 1;}}return left;}
public:vector<int> specialSort(int N) {for (int i = 0; i < N; i++) {arr.emplace_back(i + 1);}for (int k = 0; k < N; k++) {int cur = arr[k];int pos = binarySearch(k); //arr[k]应该放到pos位置for (int j = k - 1; j >= pos; j--) { //pos到k-1位置的数全部向后移动一个位置arr[j + 1] = arr[j];}arr[pos] = cur;}return arr;}
};