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

文章目录

• • 1.大赛题目
  • 2.中文翻译
  • 3.代码案例
  • 4.解题思路
  • • 4.1代码举例

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=5int n = scanner.nextInt();//m=3int m = scanner.nextInt();int A[] = new int[n];int out[] = new int[n];int B[] = new int[m];//输入Afor(int i = 0;i<A.length;i++) {A[i] = scanner.nextInt();}//输入Bfor(int i = 0;i<B.length;i++) {B[i] = scanner.nextInt();}//数组创造空间之后，默认每一个下标的值为0int 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]]等于几都可以，只要不等于0Ex[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]]等于几都可以，只要不等于0Ex[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

总结

以上是生活随笔为你收集整理的2019中国大学生程序设计竞赛(CCPC)-网络选拔赛-第七题Shuffle Card的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。