1455D Sequence and Swaps（思维）

本是古典何须时尚 2021-07-16 18:42 339阅读 0赞

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