当前位置:首页 > 题解目录 > 正文内容

【题解】小x与队列

亿万年的星光3年前 (2021-12-18)题解目录1402

【题目描述】

小X正和同学们做列队的练习。
有n名同学排成一路纵队,编号为i的同学排在从前往后数第i个位置上,即:初始时的队列为1, 2, 3, ..., n。
接下来小X会发出若干条指令,每条指令形如“请编号为x的同学排到最前面来”。(例如:若当前时刻的队列为5, 4, 3, 2, 1,发出一条x=2的指令后,队列变成了2, 5, 4, 3, 1。)
小X发出了很多很多指令,同学们晕头转向不知道该怎么排列。于是就请你算一算,执行完这些指令后,队列应该变成什么样?

【输入描述】

第一行两个用空格隔开的正整数n和m,分别表示人数和指令数。
第二行m个用空格隔开的正整数x[i],按顺序表示每次指令的x值。

【输出描述】

输出仅有一行包含n个正整数,相邻两个数之间用一个空格隔开,表示执行完所有指令后的队列。

【样例输入】

4 3
2 3 2

【样例输出】

2 3 1 4

【提示】

样例解释
第一条指令前:1 2 3 4
第一条指令后(x=2):2 1 3 4
第二条指令后(x=3):3 2 1 4
第三条指令后(x=2):2 3 1 4

【数据范围】

对于30%的数据,1<=n,m<=1000
对于另外30%的数据,n=m,且1~n每个数在x[i]中恰好出现一次。
对于100%的数据,1<=n,m<=100000

【题目分析】

  • 第一眼看上去像插入排序。每次把数放到前面去,后面数字移动一个,但是,众所周知,插入排序最大的缺点,每次移动需要花费大量的时间,然后看了一眼m的上限100000。绝对不可能这么干。

  • 数据(站队)不存在重复的情况(1,2,3,3,3,4,4,5 这种不存在),一开始一定是个顺序序列。

  • 看题目的样例,第一次给的是2,变成2 1 3 4。最后一次给的还是2。这两次给的都是2,只有最后一次是我们想要的结果,事实上,不论前面有多少个2,只有最后一次会把它排在最前面。也就是:“最后一次出现的数字一定排在最前面”。那么,依次类推,“倒数第二次出现的数字一定排在正数第二个位置”........ 。那么我们从最后一个开始遍历就行。

  • 假如从最后一个开始遍历,那么遇到相同的数字怎么办?答案就是直接跳过就行。因为“最后出现的数字一定排在最前面”的原因。后面出现相同的数字不用处理就行,如果处理了,从后往前遍历和从前往后遍历就一样了。

  • 按照上面的思路,我们可以定义一个标记数组,用来标记哪些数字出现过。没有出现过的数字直接输出(因为从后往前),同时标记一下。下次遍历的时候遇到标记过的,直接跳过就行。

  • 最后,千万别忘了,有的数字可能从来没被使用过。这些数字按照原顺序输出即可(从前往后输出)。



【参考代码】

#include<bits/stdc++.h>
using namespace std;
int n,m,flag[1000005]; //flag标记数组  
int a[1000005];//队伍 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&a[i]);
	}
	for(int i=m;i>=1;i--){ //从后往前遍历 
		if(flag[a[i]]==0){  // 如果当前这个数字没有被使用过 
			printf("%d ",a[i]);   // 没有被使用过的直接输出 
			flag[a[i]]=1;
		}
	}
	// 万一有人真的没有被使用过, 
	for(int i=1;i<=n;i++){
		if(flag[i]==0){
			printf("%d ",i);
		}
	}
	return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】翻手算法

翻手算法(fanshou.cpp) 【问题描述】 ⼩酷爱算法,他在编程珠玑⼀书中了解到了⼀种新的算法——翻⼿算法,为了更好的理解算 法,⼩明找来⼀叠纸牌,每⼀张纸牌上只有⼀个⼤写或...

【题解】取数

【题目描述】设有N 个正整数(1 <= N <= 50),其中每一个均是大于等于1、小于等于300的数。从这N个数中任取出若干个数(不能取相邻的数),要求得到一种取法,使得到的和为最大。例...

【题解】月度开销

【题目描述】农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N(1 ≤N≤ 100,000) 天里每天需要的开销。约翰打算为连续的M(1 ≤M≤N)...

【题解】求车速问题

【题目描述】一辆以固定速度行驶的汽车,司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的),为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多...

【题解】导弹拦截

【题目描述】某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导...

进制转换(1)

【题目描述】毛毛是个健忘的孩子,编程课上老师刚讲过进制转换的问题,她又忘了。请你帮他编写一个程序,完成一个浮点数与二进制之间的相互转换【输入描述】两个数字,第一个数字表示要转换的数字,浮点型。第二个是...