# AcWing 113. 特殊排序()-其他

## AcWing 113. 特殊排序()

### 提示

• $$1 \leq N \leq 1000$$

### AC Code

# include <bits/stdc++.h>
using namespace std;

# define ll long long
# define lf double
# define GO(i,a,b) for(ll i = a; i <= b; i ++)
# define RO(i,b,a) for(ll i = b; i >= a; i --)
# define CI const int
# define pii pair<int,int>
# define MP(a,b) make_pair(a, b)
# define PB push_back
# define mem(a,x) memset(a, x, sizeof a)
# define F first
# define S second

// 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> ans;
ans.PB(1);
GO (i, 2, n){
int l = 1, r = i - 1;
int pos = 0;
while (l <= r){
int mid = (l + r) >> 1;
bool res = compare(ans[mid - 1], i);
if (res){
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
ans.insert(ans.begin() + pos, i);
}
return ans;
}
};

————————

### 提示

• $$1 \leq N \leq 1000$$

### AC Code

# include <bits/stdc++.h>
using namespace std;

# define ll long long
# define lf double
# define GO(i,a,b) for(ll i = a; i <= b; i ++)
# define RO(i,b,a) for(ll i = b; i >= a; i --)
# define CI const int
# define pii pair<int,int>
# define MP(a,b) make_pair(a, b)
# define PB push_back
# define mem(a,x) memset(a, x, sizeof a)
# define F first
# define S second

// 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> ans;
ans.PB(1);
GO (i, 2, n){
int l = 1, r = i - 1;
int pos = 0;
while (l <= r){
int mid = (l + r) >> 1;
bool res = compare(ans[mid - 1], i);
if (res){
pos = mid;
l = mid + 1;
}
else r = mid - 1;
}
ans.insert(ans.begin() + pos, i);
}
return ans;
}
};