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

相关内容

热门资讯

鸿蒙系统和安卓图标,图标设计中... 你知道吗?最近手机界可是掀起了一股不小的波澜呢!那就是华为的鸿蒙系统,还有那些让人眼前一亮的安卓图标...
电脑刷台电安卓系统,轻松实现多... 你有没有发现,最近你的电脑是不是越来越不给力了?打开网页慢吞吞的,下载个文件像蜗牛爬行。别急,让我来...
安卓系统会老化吗,揭秘其老化现... 你有没有发现,你的安卓手机用久了,有时候反应慢吞吞的,就像一个老态龙钟的老人,是不是在怀疑,安卓系统...
原生安卓系统8精简,体验升级 亲爱的读者们,你是否曾为手机系统臃肿、运行缓慢而烦恼?今天,就让我带你一探究竟,揭开原生安卓系统8的...
安卓4.3系统老不老,探索经典... 你有没有发现,手机里的安卓4.3系统好像已经很久远了,是不是觉得它有点“老气横秋”呢?今天,我们就来...
阿里的云系统和安卓系统,构建未... 你知道吗?在科技的世界里,两大巨头——阿里的云系统和安卓系统,就像两颗璀璨的星星,各自散发着独特的光...
安卓系统 网络访问控制,安卓系... 你有没有发现,现在手机里的安卓系统越来越智能了?不过,智能归智能,安全还是要放在第一位哦!今天,就让...
安卓系统日历排班表,轻松规划工... 你有没有发现,每天忙碌的生活中,时间就像个调皮的小精灵,总是在不经意间溜走。为了更好地把握时间,合理...
安卓游戏账号鸿蒙系统,畅游新生... 你有没有想过,你的安卓游戏账号在鸿蒙系统上也能畅玩无阻?没错,就是那个让华为手机焕然一新的鸿蒙系统!...
努比亚支持安卓系统吗,畅享智能... 你有没有想过,手机的世界里,努比亚这个品牌是不是也支持安卓系统呢?毕竟,安卓系统可是智能手机界的“老...
安卓6系统小游戏,畅享指尖乐趣 你有没有发现,手机里的安卓6系统竟然藏着那么多好玩的小游戏?没错,就是那个看似普通,实则暗藏玄机的操...
安卓充值系统怎么换成苹果系统,... 你是不是也和我一样,对安卓系统爱得深沉,但又忍不住对苹果系统的流畅和独特功能心动不已?别急,今天就来...
小米安卓切换苹果系统,探索全新... 你知道吗?最近有个大新闻在科技圈里炸开了锅,那就是小米手机用户竟然开始尝试将安卓系统切换到苹果系统。...
老电脑改装安卓系统,改装安卓系... 你那台老电脑是不是已经服役多年,性能越来越不给力了?别急,今天就来教你怎么给它来个华丽变身——改装成...
安卓组态系统是什么,安卓组态系... 你有没有听说过安卓组态系统?这可是个在科技圈里悄悄走红的小秘密哦!想象你手中拿着一部安卓手机,轻轻一...
安卓系统恢复饮食app,助您重... 你是不是也和我一样,手机里装了各种APP,但有时候感觉胃里像是被小怪兽抓挠,食欲不振,体重也跟着“涨...
安卓子系统不能运行,安卓子系统... 最近我的安卓手机有点儿闹脾气呢!你有没有遇到过这种情况:手机里某个子系统突然不能正常运行了?别急,让...
塞班系统转安卓教程,轻松实现跨... 你有没有想过,把你的老塞班手机升级到安卓系统,让它焕发第二春呢?这可不是什么难事,只要跟着我一步步来...
原生安卓系统电视推荐,解锁智能... 亲爱的电视迷们,你是不是已经厌倦了那些花哨却不够实用的智能电视?想要一台纯粹、原生、性能卓越的安卓系...
平板系统重装 安卓,安卓系统安... 亲爱的读者,你是不是也和我一样,对平板电脑的安卓系统重装充满了好奇和期待呢?想象当你手中的平板焕然一...