【题解】小x与队列
【题目描述】
小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; }
扫描二维码推送至手机访问。
版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。