算法
(模拟) $O(n^2)$
首先替换的下标必定递增,否则会出现逆序对,那么从前往后模拟一遍,检查是否排好序就行了。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::swap;
int main() {
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> x;
vector<int> a(n);
for (auto& it : a) cin >> it;
int cnt = 0;
for (int i = 0; i < n && !is_sorted(a.begin(), a.end()); ++i) {
if (a[i] > x) {
swap(a[i], x);
cnt++;
}
}
cout << (!is_sorted(a.begin(), a.end()) ? -1 : cnt) << '\n';
}
return 0;
}