题目传送门

sol1：拿到这题的时候刚上完课，讲的是指针。所以一下子就联想到了双向链表。链表可以解决卡片移动的问题，但是无法快速定位要移动的卡片，所以再开一个指针数组，结合数组下标访问的特性快速定位到要移动的卡片。把链表和数组的优势结合起来；

双向链表

#include "bits/stdc++.h"

using namespace std;

const int MAXN = 1e5 + ;

struct Node {

    Node* pre;

    int num;

    Node* nxt;

};

Node* a[MAXN];

int main() {

    int n, m, k;

    scanf("%d%d", &n, &m);

    a[] = new(Node);

    for (int i = ; i <= n; i++) {

        a[i] = new(Node);

        a[i]->pre = a[i - ];

        a[i - ]->nxt = a[i];

        scanf("%d", &a[i]->num);

    }

    a[n + ] = new(Node);

    a[n + ]->pre = a[n];

    a[n]->nxt = a[n + ];

    for (int i = ; i <= m; i++) {

        scanf("%d", &k);

        a[k]->nxt->pre = a[k]->pre;

        a[k]->pre->nxt = a[k]->nxt;

        a[]->nxt->pre = a[k];

        a[k]->nxt = a[]->nxt;

        a[]->nxt = a[k];

        a[k]->pre = a[];

    }

    for (Node* i = a[]->nxt; i != a[n + ]; i = i->nxt)

        printf("%d ", i->num);

    return ;

}

sol2：比赛结束后看了别人的题解，发现还可以用栈来实现。越晚操作的牌就在牌堆的越上面。所以只要把牌堆的操作倒着输出就好了，如果这个数已经输出过就不用输了。

栈

#include "bits/stdc++.h"

using namespace std;

const int MAXN = 2e5 + ;

int stk[MAXN];

bool vis[MAXN];

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = n; i >= ; i--)

        scanf("%d", &stk[i]);

    for (int i = n + ; i <= n + m; i++)

        scanf("%d", &stk[i]);

    for (int i = n + m; i >= ; i--) {

        if (vis[stk[i]]) continue;

        printf("%d ", stk[i]);

        vis[stk[i]] = true;

    }

    return ;

}

巴特西

HDU-6707-Shuffle Card(很数据结构的一道题)

题目传送门

最新文章

热门文章