Educational Codeforces Round 99 (Rated for Div. 2) D. Sequence and Swaps
创始人
2024-05-02 01:00:01
0

翻译:

您将得到一个序列𝑎,该序列由𝑛个整数𝑎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
#include
#include
#include
#include
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}int a[505],m;
int pd(){for (int i =2; i<=n; i++) {if (a[i-1]>a[i]) {return 0;}}return 1;
}
void wanyurukong(){cin>>n>>m;for (int i =1; i<=n; i++) {cin>>a[i];}if (pd()) {printf("0\n");return;}int ff=0;for (int i =1; i<=n; i++) {if (a[i]>m) {ff++;swap(a[i], m);}if (pd()) {printf("%d\n",ff);return;}}printf("-1\n");}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {wanyurukong();}//wanyurukongreturn 0;
}

相关内容

热门资讯

安卓系统自带的网页,功能与特色... 你有没有发现,每次打开安卓手机,那熟悉的系统界面里总有一个默默无闻的小家伙——安卓系统自带的网页浏览...
美咖云系统安卓版,开启智能生活... 你有没有发现,最近手机上多了一个叫“美咖云系统安卓版”的小家伙?它就像一个魔法师,轻轻一点,就能让你...
安卓系统推荐最好的手机,盘点性... 你有没有想过,拥有一部性能卓越的手机,就像是拥有了移动的宝藏库?在这个信息爆炸的时代,一部好手机不仅...
安卓11系统能精简吗,释放潜能 你有没有发现,随着手机越来越智能,系统也越来越庞大?安卓11系统,这个最新的操作系统,是不是也让你觉...
安卓自动重启系统软件,揭秘原因... 手机突然自动重启,是不是感觉整个人都不好了?别急,今天就来和你聊聊这个让人头疼的安卓自动重启系统软件...
苹果手机x刷安卓系统,探索安卓... 你有没有想过,你的苹果手机X竟然也能刷上安卓系统?是的,你没听错,就是那个一直以来都和我们苹果手机X...
安卓系统智商低吗,智商低下的真... 你有没有想过,为什么安卓系统的智商总被调侃得好像有点低呢?是不是觉得它总是慢吞吞的,有时候还犯点小错...
安卓系统手机联系人,揭秘你的社... 你有没有发现,手机里的联系人列表就像是一个小小的社交圈呢?里面藏着我们的亲朋好友、工作伙伴,甚至还有...
安卓系统免费铃声下载,打造个性... 手机里那首老掉牙的铃声是不是让你觉得有点out了呢?别急,今天就来给你支个招,让你轻松给安卓手机换上...
安卓系统用哪个桌面好,打造个性... 你有没有发现,手机桌面可是我们每天都要面对的“脸面”呢?换一个好看的桌面,心情都能跟着好起来。那么,...
虚拟大师是安卓10系统,功能与... 你知道吗?最近在手机圈里,有个新玩意儿引起了不小的轰动,那就是虚拟大师!而且,更让人惊喜的是,这个虚...
安卓系统与苹果优缺点,系统优缺... 说到手机操作系统,安卓和苹果绝对是两大巨头,它们各有各的特色,就像两道不同的美味佳肴,让人难以抉择。...
安卓win双系统主板,融合与创... 你有没有想过,一台电脑如果既能流畅运行安卓系统,又能轻松驾驭Windows系统,那该有多爽啊?没错,...
安卓系统可精简软件,轻松提升手... 你有没有发现,手机里的安卓系统越来越庞大,软件也越装越多,有时候感觉手机就像个“大肚子”,不仅运行速...
安卓系统基于linux的代码,... 你有没有想过,那个陪伴你每天刷抖音、玩游戏、办公的安卓系统,其实背后有着一套复杂的基于Linux的代...
苹果和安卓的拍照系统,谁更胜一... 你有没有发现,现在手机拍照已经成为我们生活中不可或缺的一部分呢?无论是记录生活的点滴,还是捕捉美丽的...
苹果和安卓系统不同吗,系统差异... 你有没有想过,为什么你的手机里装的是苹果的iOS系统,而朋友的手机却是安卓系统呢?这两种系统,看似都...
安卓系统有多少级,揭秘其多级架... 你有没有想过,那个陪伴我们日常生活的安卓系统,它其实有着丰富的层级结构呢?没错,就是那个让我们的手机...
华为鸿蒙系统与安卓的,技术融合... 你知道吗?最近科技圈可是炸开了锅,华为鸿蒙系统与安卓的较量成为了大家热议的话题。这不,今天我就来给你...
什么安卓手机是苹果系统,搭载苹... 你有没有想过,为什么有些人宁愿花大价钱买苹果手机,而有些人却对安卓手机情有独钟呢?其实,这个问题背后...