题解 | #跑步训练#

双向链表加hashmap，利用map快速定位出队的第一个人，然后利用链表快速重排表示插队结果。
主要参考LRU算法
时间复杂度：其中map定位是O(1)，链表重排也是O(1)，每次插队需要寻找插队的最后一个节点，所以O(x)。
欢迎指正！

#include <iostream>
#include <unordered_map>

using namespace std;

struct DLinkedNode {
    int value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _value): value(_value), prev(nullptr), next(nullptr) {}
};

class DLinkList {
public:
    unordered_map<int, DLinkedNode*> cache; // map保存每个人的编号到具体节点的映射
    int size;
    DLinkedNode* head;
    DLinkedNode* tail;

    DLinkList(int n);

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void insert(int start, int x);
};

DLinkList::DLinkList(int n){
    head = new DLinkedNode();
    tail = new DLinkedNode();
    head->next = tail;
    tail->prev = head;
    for(int i = n; i >= 1; i--){
        DLinkedNode* node = new DLinkedNode(i);
        cache[i] = node;
        addToHead(node);
    }
}

void DLinkList::insert(int start, int x){
    DLinkedNode* start_node = cache[start];
    DLinkedNode* end_node = start_node;
    while(x > 0 && end_node->next != tail){
        end_node = end_node->next;
        x--;
    }
    start_node->prev->next = end_node->next;
    end_node->next->prev = start_node->prev;
    start_node->prev = head;
    end_node->next = head->next;
    head->next->prev = end_node;
    head->next = start_node;
}

int main(void){
    int n, q;
    cin >> n >> q;
    DLinkList dll(n);
    for(int i = 0; i < q; i++){
        int start, x;;
        cin >> start >> x;
        dll.insert(start, x);
    }
    auto cur = dll.head;
    for(cur = cur->next; cur != dll.tail; cur = cur->next){
        cout << cur->value << " ";
    }
    cout << endl;
    return 0;
}