|
|
##[$AcWing$ $113$. 特殊排序](https://www.acwing.com/problem/content/description/115/)
|
|
|
|
|
|
**[前导知识](https://www.cnblogs.com/littlehb/p/17137028.html)**
|
|
|
|
|
|
### 一、题目描述
|
|
|
有 $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$嘛。
|
|
|
|
|
|
采用 **[二分插入排序](https://www.cnblogs.com/littlehb/p/17137028.html)** 解决该问题:
|
|
|
- 本题中不体现对值的使用，因为隐藏的$compare$中才会有这个 **值** 的概念，我们不关心,我们只关心序号
|
|
|
- 将第一个元素序号压入向量里，然后枚举后续的每一个序号，二分查找合适的位置$r$
|
|
|
|
|
|
### 五、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#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;
|
|
|
}
|
|
|
};
|
|
|
```
|
|
|
|
