【题目描述】

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

(adsbygoogle = window.adsbygoogle || []).push({});