# 10/3 資結小考 參考題解

## Problem 810

**題目：**
- N個便當疊成一堆，有K種口味(1到K)
- 只能賣最上面的便當
- N個客人排隊，每人想要特定口味
- 購買過程：
- 如果最上面便當是想要的口味→買走離開
- 如果不是→回到隊伍最後重新排隊
- 直到最上面便當沒有任何排隊的人想要時停止
- 輸出：最終買不到便當的人數

**子題限制：**
- 子題1 (20%): n ≤ 10, k ≤ 10
- 子題2 (30%): n ≤ 100
- 子題3 (50%): 1 ≤ n ≤ 10^7, 1 ≤ k ≤ 1000

### 暴力解(50%)

以最簡單直覺的想法: 做兩個deque來直接模擬排隊和便當的狀況。
每次檢查最上面便當時，就遍歷整個隊伍找想要的客人。
時間複雜度O(N²)，子題1,2可過，但子題3會TLE。

#include <stdio.h>
#include <stdlib.h>

#define maxN 10000005
#define maxK 1005

typedef struct {
    int data[maxN];
    int front, rear, size;
} Deque;

Deque list;
Deque queue;
int people[maxK];

void init(Deque* dq) {
    dq->front = 0;
    dq->rear = 0;
    dq->size = 0;
}

int empty(Deque* dq) {
    return dq->size == 0;
}

void push_back(Deque* dq, int value) {
    dq->data[dq->rear] = value;
    dq->rear = (dq->rear + 1) % maxN;
    dq->size++;
}

void push_front(Deque* dq, int value) {
    dq->front = (dq->front - 1 + maxN) % maxN;
    dq->data[dq->front] = value;
    dq->size++;
}

int pop_front(Deque* dq) {
    if (empty(dq)) return -1;
    int value = dq->data[dq->front];
    dq->front = (dq->front + 1) % maxN;
    dq->size--;
    return value;
}

int pop_back(Deque* dq) {
    if (empty(dq)) return -1;
    dq->rear = (dq->rear - 1 + maxN) % maxN;
    int value = dq->data[dq->rear];
    dq->size--;
    return value;
}

int peek_back(Deque* dq) {
    if (empty(dq)) return -1;
    return dq->data[(dq->rear - 1 + maxN) % maxN];
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    
    init(&list);
    init(&queue);
    
    for (int i = 0; i < N; i++) {
        int tmp;
        scanf("%d", &tmp);
        push_back(&list, tmp);
    }
    
    for (int i = 0; i < N; i++) {
        int tmp;
        scanf("%d", &tmp);
        push_back(&queue, tmp);
        people[tmp]++;
    }
    
    while (!empty(&queue)) {
        int now = peek_back(&list);
        
        if (people[now] == 0) {
            break;
        }
        
        int found = 0;
        int queueSize = queue.size;
        
        for (int i = 0; i < queueSize; i++) {
            int customer = pop_front(&queue);
            
            if (customer == now && !found) {
                pop_back(&list);
                people[now]--;
                found = 1;
            } else {
                push_back(&queue, customer);
            }
        }
        
        if (!found) break;
    }
    
    printf("%d\n", queue.size);
    
    return 0;
}

### 解法(100%AC)

觀察第三個子題，N最大是1e7，原先作法肯定會TLE。從最壞情況觀察，每個便當都可能需要排隊輪過一輪才知道是否結束，意味著隊伍裡已經沒有想要買該口味便當的顧客。可以建立K大小的查表，記錄每種口味需求人數，不再需要花費O(N)時間維護排隊。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxN 10000000
#define maxK 1000

int people[maxK+5] = {0};
int list[maxN+5];
int pt = 0;

int main(){
    int N, K;
    scanf("%d %d", &N, &K);
    int tmp;

    for(int i=0; i<N; i++){
        scanf("%d", &tmp);
        list[pt++] = tmp;
    }

    for(int i=0; i<N; i++){
        scanf("%d", &tmp);
        people[tmp]++;
    }

    for(int i=0; i<N; i++){
        int now = list[pt-1];

        if(!people[now]) break;
        else people[now]--;

        pt--;
    }

    int count = pt;
    
    printf("%d", count);
}

---

## Problem 811

**題目：**
- N個觀眾排隊，編號1到N (1 ≤ N ≤ 10^5)
- Q個指令 (1 ≤ Q ≤ 10^5)
- 每個指令包含兩個數字A和B
- 將編號A到編號B的所有觀眾移動到隊伍最後面
- 保證A和B都在隊伍中，且執行時A的位置 ≤ B的位置
- 移動的觀眾之間相對位置保持不變
- 輸出：執行完所有指令後的最終排列順序

**子題限制：**
- 子題1 (20分): n ≤ 10, q ≤ 10
- 子題2 (30分): n ≤ 1000, q ≤ 1000
- 子題3 (50分): 1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5

### 暴力解(50%)

以最直覺的想法: 建立linkedlist，手動將目標數值位置找出，並一個一個丟到最後面。時間複雜度較高，測資除了最後一筆外都會過。

//測資除了最後一筆外都會過，可見助教有多仁慈
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node* prev;
    struct Node* next;
} Node;

Node* head = NULL;
Node* tail = NULL;
int N, Q;

// 創建新節點
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 找到值為value的節點
Node* findNode(int value) {
    Node* current = head;
    while (current != NULL) {
        if (current->value == value) return current;
        current = current->next;
    }
    return NULL;
}

// 移除一個節點
void removeNode(Node* node) {
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        head = node->next;
    }
    
    if (node->next != NULL) {
        node->next->prev = node->prev;
    } else {
        tail = node->prev;
    }
    
    node->prev = node->next = NULL;
}

// 將節點加到最後面
void appendNode(Node* node) {
    if (tail != NULL) {
        tail->next = node;
        node->prev = tail;
    } else {
        head = node;
        node->prev = NULL;
    }
    
    tail = node;
    node->next = NULL;
}

int main() {
    scanf("%d %d", &N, &Q);
    
    // 建立初始鏈結串列
    for (int i = 0; i < N; i++) {
        int value;
        scanf("%d", &value);
        
        Node* newNode = createNode(value);
        
        if (head == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }
    
    // 處理Q個操作
    for (int i = 0; i < Q; i++) {
        int A, B;
        scanf("%d %d", &A, &B);
        
        // 從A開始，一個一個拿到後面
        Node* current = findNode(A);
        Node* endNode = findNode(B);
        
        while (current != NULL) {
            Node* next = current->next;
            
            // 移除當前節點
            removeNode(current);
            // 加到最後面
            appendNode(current);
            
            // 如果到達B就停止
            if (current == endNode) break;
            current = next;
        }
    }
    
    // 輸出結果
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->value);
        current = current->next;
    }
    printf("\n");
    
    // 釋放記憶體
    current = head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    
    return 0;
}

### Array_Linkedlist解(100%AC)

從第三個子題來看，N和Q上限是1e5，O(NQ)肯定會超時，因此需要優化。題目條件「相對位置不變」很重要，以linkedlist特性來看，只需對切割區間的頭尾做操作，複雜度O(1)，問題在於如何找到數字。
依題目敘述，數字是1~N，可以利用array連續記憶體特性，在array上模擬linkedlist，每個index代表每個數字，不再需要花線性時間尋找數字，使得對數字直接操作成為可能。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxN 100000
#define PREV 0
#define NEXT 1

int N, Q;
int nodes[maxN + 10][2];  // [i][PREV] = 前一個節點, [i][NEXT] = 後一個節點
int head = -1;
int tail = -1;

int main() {
    scanf("%d %d", &N, &Q);
    
    memset(nodes, -1, sizeof(nodes));
    
    // 建立初始鏈結串列
    int prev = -1;
    int current;
    
    for (int i = 0; i < N; i++) {
        scanf("%d", &current);
        
        if (head == -1) {
            head = current;
        } else {
            nodes[current][PREV] = prev;
            nodes[prev][NEXT] = current;
        }
        
        prev = tail = current;
    }

    // 處理 Q 個查詢
    int rangeStart, rangeEnd;
    
    for (int i = 0; i < Q; i++) {
        scanf("%d %d", &rangeStart, &rangeEnd);
        
        int prevOfStart = nodes[rangeStart][PREV];
        int nextOfEnd = nodes[rangeEnd][NEXT];
        
        // 特殊情況：如果要移動的已經在最後面，跳過
        if (head == rangeStart && nextOfEnd == -1) {
            continue;
        }
        
        // 切斷區間：修復切斷後的連結
        if (prevOfStart != -1) {
            nodes[prevOfStart][NEXT] = nextOfEnd;
        } else {
            head = nextOfEnd;  // rangeStart 是第一個節點
        }
        
        if (nextOfEnd != -1) {
            nodes[nextOfEnd][PREV] = prevOfStart;
        } else {
            tail = prevOfStart;  // rangeEnd 是最後一個節點
        }
        
        // 將切斷的區間接到尾巴
        nodes[tail][NEXT] = rangeStart;
        nodes[rangeStart][PREV] = tail;
        nodes[rangeEnd][NEXT] = -1;
        tail = rangeEnd;
    }

    // 輸出最終結果
    current = head;
    while (current != -1) {
        printf("%d ", current);
        current = nodes[current][NEXT];
    }
    printf("\n");
    
    return 0;
}