HDUOJ 6707 Shuffle Card

题目链接

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<=1e5）

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

思维题，在线洗牌肯定会 T，因为没有一个很好的数据结构可以完成此题。我们不妨换一种思维，把洗牌顺序记录下来，不难发现，最后一次洗的牌一定在第一张，倒数第二次在第二张，以此类推，我们标记一下洗过的牌，最后没洗的保持原顺序插入答案数组即可，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N],op[N],vis[N];
vector<int>ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++) scanf("%d",&op[i]);
    for(int i=m;i>=1;i--){
        if(!vis[op[i]]){
            ans.push_back(op[i]);
            vis[op[i]]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[a[i]]) ans.push_back(a[i]);
    }
    for(auto i:ans) printf("%d ",i);
}