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