Shuffle Card

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 507    Accepted Submission(s): 257

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6707

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

 

 

Source

2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

 

 

题目意思：

桌上有n张卡，每张卡的编号是从1~n上的不同的数，对原来给出的顺序执行m次操作，每次操作将一张编号为si的卡放到第一张卡前面。

解题思路：

将给出的每张牌记录一下编号和当前给出顺序的位置，然后按编号排个序，进行m次操作，每次操作将该编号的位置的值变为最小的位置值-1，相当于放在第一张牌之前。然后按照位置的值进行排序，就得到答案了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int M = 1e5 + 50;
pair<int,int> a[M];
bool cmp1(pair<int,int> x, pair<int,int> y){
	return x.first < y.first; 
}
bool cmp2(pair<int,int> x, pair<int,int> y){
	return x.second < y.second; 
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 0; i < n; i++){
		int d = 0;
		scanf("%d",&d);
		a[i].first = d;
		a[i].second = i;
	}
	sort(a,a+n,cmp1);	//按编号进行排序 
	int s = 0;	//记录当前最小的位置 
	for(int i = 0; i < m;i++){
		int d = 0;
		scanf("%d",&d);
		a[d-1].second = (--s); 
	}
	sort(a,a+n,cmp2);	//按位置的值进行排序 
	for(int i = 0; i < n; i++){
		printf("%d ",a[i].first);	//输出答案，注意格式没有换行，每个编号后面带空格 
	}
	return 0;
}