题目链接：https://codeforc.es/contest/1455/problem/D
You are given a sequence a consisting of n integers a1,a2,…,an, and an integer x. Your task is to make the sequence a sorted (it is considered sorted if the condition a1≤a2≤a3≤?≤an holds).
To make the sequence sorted, you may perform the following operation any number of times you want (possibly zero): choose an integer i such that 1≤i≤n and ai>x, and swap the values of ai and x.
For example, if a=[0,2,3,5,4], x=1, the following sequence of operations is possible:
choose i=2 (it is possible since a2>x), then a=[0,1,3,5,4], x=2;
choose i=3 (it is possible since a3>x), then a=[0,1,2,5,4], x=3;
choose i=4 (it is possible since a4>x), then a=[0,1,2,3,4], x=5.
Calculate the minimum number of operations you have to perform so that a becomes sorted, or report that it is impossible.
Input
The first line contains one integer t (1≤t≤500) — the number of test cases.
Each test case consists of two lines. The first line contains two integers n and x (1≤n≤500, 0≤x≤500) — the number of elements in the sequence and the initial value of x.
The second line contains n integers a1, a2, …, an (0≤ai≤500).
The sum of values of n over all test cases in the input does not exceed 500.
Output
For each test case, print one integer — the minimum number of operations you have to perform to make a sorted, or ?1, if it is impossible.
Example
input
6
4 1
2 3 5 4
5 6
1 1 3 4 4
1 10
2
2 10
11 9
2 10
12 11
5 18
81 324 218 413 324
output
3
0
0
-1
1
3
题意
对于一个长度为 n 的数组，每次步骤可以将一个元素 a[i] 与 x 互换（前提是 ai > x），求至少需要换几次使得数列成为非递减序列。
分析
我们发现每次交换以后都只能将一个位置上的数变小，并且一旦交换，这个位置的数就不能再变了（因为不比 x 大了），所以可以推断出，如果连续下降序列大于 2 ，就不可能通过操作使他变成非递减的了。
对于一个位置 i ，若 a[i] < a[i+1] ，那这个点就必须要通过交换来变小，如果交换会使得 a[i - 1] > a[i] 了，那么要先交换前面的一系列点，使得交换过后仍是非递减数列。
代码
#include<bits/stdc++.h>
using namespace std;int t;
int n,x;
int a[507];
int f[507];int main()
{
scanf("%d",&t);while(t--){
int ans = 0;scanf("%d%d",&n,&x);for(int i=1;i<=n;i++) scanf("%d",&a[i]), f[i] = 0;int flag = 1;for(int i=1;i<n;i++){
if(a[i] > a[i + 1]){
if(f[i - 1] == 1) flag = 0;f[i] = 1;}}if(flag == 0){
printf("-1\n");continue;}for(int i=1;i<n;i++){
if(f[i] == 0) continue;int j = i;while(a[j - 1] > x && j - 1 > 0) j--;if(j == i && a[i] <= x){
flag = 0;break;}for(int k=j;k<=i;k++){
if(x == a[k]) continue;//注意这边如果相等的不用交换 swap(x, a[k]);ans++;}if(a[i] > a[i + 1]){
flag = 0;break;}}if(flag == 1) printf("%d\n",ans);else printf("-1\n");}return 0;
}