2019中国大学生程序设计竞赛(CCPC)-网络选拔赛-第七题Shuffle Card

1.大赛题目

Shuffle Card
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 6695 Accepted Submission(s): 2061

Problem Description
A deck of card consists of n cards. Each card is different, numbered from 1 to n. At first, the cards were ordered from 1 to n. We complete the shuffle process in the following way, In each operation, we will draw a card and put it in the position of the first card, and repeat this operation for m times.

Please output the order of cards after m operations.

Input
The first line of input contains two positive integers n and m.（1<=n,m<=105）

The second line of the input file has n Numbers, a sequence of 1 through n.

Next there are m rows, each of which has a positive integer si, representing the card number extracted by the i-th operation.

Output
Please output the order of cards after m operations. (There should be one space after each number.)

Sample Input
5 3
1 2 3 4 5
3
4
3

Sample Output
3 4 1 2 5

2.中文翻译

洗牌。
时间限制：2000/1000毫秒（Java /其他）内存限制：65536/65536 K（Java /其他）
总提交量：6695份接受的提交量：2061份

问题

一副牌由N张牌组成。每一张牌都是不同的，编号从1到N。首先，牌是从1到N排列的。我们按照以下方式完成洗牌过程，在每一个操作中，我们将画一张牌并将其放在第一张牌的位置上，然后重复操作m次。

请在M操作后输出卡的顺序。

输入

输入的第一行包含两个正整数n和m。

输入文件的第二行有n个数字，从1到n的序列。

接下来有m行，每行都有一个正整数si，表示第i个操作提取的卡号。

输出

请在M操作后输出卡的顺序。（每个数字后面应该有一个空格。）

样本输入

5 3
1 2 3 4 5
3
4
3

样本输出

3 4 1 2 5

3.代码案例

public class sixtest {
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		//n=5
		int n = scanner.nextInt();
		//m=3
		int m = scanner.nextInt();
		int A[] = new int[n];
		int out[] = new int[n];
		int B[] = new int[m];
		//输入A
		for(int i = 0;i<A.length;i++) {
			A[i] = scanner.nextInt();
		}
		//输入B
		for(int i = 0;i<B.length;i++) {
			B[i] = scanner.nextInt();
		}
		//数组创造空间之后，默认每一个下标的值为0
		int Ex[] = new int [100010];
		int count = 0;
		//把要抽选的牌按照从后到前的顺序装进数组out中，重复的略过，然后再把剩余的装进之后的数组下标
		for(int i = B.length-1; i >= 0; i--) {
			if(Ex[B[i]]==0) {
				out[count++] = B[i];
				//这里Ex[B[i]]等于几都可以，只要不等于0
				Ex[B[i]] = 1;
			}
		}
		for(int i = 0;i<A.length;i++) {
			if(Ex[A[i]]==0) {
				out[count++] = A[i];
			}
		}
		for(int i = 0;i<out.length;i++) {
			System.out.print(out[i]+" ");
		}
		scanner.close();
	}
}

4.解题思路

像下面这样把要抽取的牌一张一张的放到最前面，后面的依次往后，可以抽相同的牌
->12345
->32145
->43125
->34125
把要抽选的牌按照从后到前的顺序装进数组out中，重复的略过，然后再把剩余的装进剩余的数组下标

4.1代码举例

for(int i = B.length-1; i >= 0; i--) {
	if(Ex[B[i]]==0) {
		out[count++] = B[i];
		//这里Ex[B[i]]等于几都可以，只要不等于0
		Ex[B[i]] = 1;
	}
}

Ex[3] = 0->out[1] = 3->Ex[3] = 1
Ex[4] = 0->out[2] = 4->Ex[4] = 1
Ex[3] = 1 ->结束循环

for(int i = 0;i<A.length;i++) {
	if(Ex[A[i]]==0) {
		out[count++] = A[i];
	}
}

Ex[1] = 0->out[3] = 1
Ex[2] = 0->out[4] = 2
Ex[3] = 1
Ex[4] = 1
Ex[5] = 0->out[5] = 5