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

#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;
    }
};