目录
题目连接：113. 特殊排序 - AcWing题库
题目描述
有 N 个元素，编号 1,2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是 N个点与 N×(N−1)/2 条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 1000010000 次提问来获取信息，每次提问只能了解某两个元素之间的关系。现在请你把这 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]题目解析
这道题采用的思想是二分，设先已排好序的数组q，当前要插入的数字为 i ，我们需比较q[mid]和 i ，如果 i 较小，我们可以证明在[ 0 , mid -1]中一定有可以填它的位置。如果在这个区间内没有比 i 小的数字，那么i 填在数组的开头；如果有比 i 小的位置，那么我们一定可以找到一个位置可以满足条件，因为q[mid]是大于 i 的，保证了右边一定有大于 i 的数字。反之若 i 比q[mid] 大，则可以证明在后面的区间内一定有满足条件的点。
在此二分中我们是保证一边一定有解，但是并不确定另一边有没有解，并且只是其中局部满足大小关系，在整体并不满足大小关系。
代码
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res(1,1);
for(int i=2;i<=N;i++){
int l=0,r=res.size()-1;
while(l<r){
int mid = r+l+1>>1;
if(compare(res[mid],i)) l=mid;
else r=mid-1;
}
res.push_back(i);
for(int j=res.size()-2;j>r;j--) swap(res[j],res[j+1]);
if(compare(res[r+1],res[r])) swap(res[r],res[r+1]);
}
return res;
}
};代码解析
在代码中我们通过二分找到一个位置使得该位置的左边一个数字小于它，右边一个数字大于它，所以第r个数字理论来说是小于它的，所以我们只需要从r+1开始逆置就好了。但是有可能r=0，这就有可能这个数字应该加在开头，所以还要比较一下r和r+1位置上的数字。