1455D Sequence and Swaps（思维）

D. Sequence and Swaps
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

思路：对于一个排列如果我们想其排好序，且只能使用x与ai交换（x<ai）。初始sum=0，我们从i开始遍历到n，对于每一个(1)如果已经排好序则退出遍历，输出sum.(2)如果没有排好序，设对于从i到n的序列中的所有元素加上x的集合中最小的元素为k，<1>如果k= =ai,则无需进行操作，继续向后遍历，<2>如果k!=ai&&k!=x，在这种情况下可以发现我们想通过x与排列ai到an的最小元素（值为k）交换使得ai成为最小的是不可能实现的，因为x>k,不满***换条件，所以那个值为k的最小元素被永远留在了后面，不可能交换到应该在的位置，退出遍历，输出-1。<3>如果k==x，x与ai进行交换，sum++,继续遍历。细实现见代码。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 2e5 + 5;
int lst[Max];
int dp[505][505];

int main()
{
   
	FAST;
	int t;cin >> t;
	while (t--)
	{
   
		int n, x;cin >> n >> x;
		for (int i = 1;i <= n;i++)cin >> lst[i];
		int g = 0;int f = 1;int ans = 1;
		for (int i = 1;i <= n;i++)
		{
   
			f = 0;
			for (int j = i;j <= n;j++)if (lst[j] < lst[j - 1])f = 1;
			if (f == 0)break;
			int k = x;
			for (int j = i;j <= n;j++)k = min(k, lst[j]);
			if (k == lst[i])continue;
			if (k != x){
   ans = 0;break;}
			g++;x = lst[i];
		}
		if (ans == 0)cout << -1 << endl;
		else cout << g << endl;
	}
}