翻译:
您将得到一个序列𝑎,该序列由𝑛个整数𝑎1、𝑎2、…、𝑎𝑛和一个整数𝑥组成。您的任务是使序列𝑎排序(如果条件𝑎1≤𝑎2≤𝑎3≤⋯≤𝑎𝑛存在,则认为该序列已排序)。
为了使序列排序,您可以执行以下操作任意次(可能是0次):选择一个整数𝑖,使1≤𝑖≤𝑛和𝑎𝑖>𝑥,并交换𝑎𝑖和𝑥的值。
例如,如果𝑎=[0,2,3,5,4],𝑥=1,则可能有以下操作顺序:
选择𝑖= 2(可能因为𝑎2 >𝑥),然后𝑎=[0、1、3、5、4],𝑥= 2;
选择𝑖= 3(可能因为𝑎3 >𝑥),然后𝑎=[0、1、2、5、4],𝑥= 3;
选择𝑖= 4(可能因为𝑎4 >𝑥),然后𝑎=[0,1,2,3,4),𝑥= 5。
计算您必须执行的最小操作数量,以便𝑎被排序,或者报告这是不可能的。
输入
第一行包含一个整数𝑡(1≤𝑡≤500)——测试用例的数量。
每个测试用例由两行组成。第一行包含两个整数𝑛和𝑥(1≤𝑛≤500,0≤𝑥≤500)——序列中的元素个数和𝑥的初始值。
第二行包含𝑛个整数𝑎1,𝑎2,…,𝑎𝑛(0≤𝑎𝑖≤500)。
输入中所有测试用例中𝑛的值之和不超过500。
输出
对于每个测试用例,打印一个整数——使𝑎排序所需执行的最小操作数,如果不可能,则打印−1。
例子
inputCopy
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
outputCopy
3.
0
0
-1
1
3.
思路:
数据范围比较小,我们来确实排列是否符合,可以直接暴力判断。如果一个不符合,我们需要替换,但是替换的时候前边的也要满足条件。而且我们不能先换大的,再换小的,因为交换有要求a[i]>x,才可以替换。所以我们从前往后如果可以替换就替换掉,因为如果可以替换的话,x就是小于a[i]的,如果替换了后边的大的,还是不符合,所以随着我们不断替换,前边的序列会越来越小,之后大可以替换比前边大的。有点绕,需要仔细想一下
代码:
/*Looking! The blitz loop this planet to search wayOnly my RAILGUN can shoot it 今すぐ身体中を 光の速さで駆け巡った確かな予感掴め! 望むものなら残さず輝ける自分らしさで信じてるよ あの日の誓いをこの瞳に光る涙それさえも 強さになるから*/
#include
#include
#include
#include
#include
#include
#include
#include
#include