程式設計題解析：隊列元素插入問題 (ID 1807)

問題背景

這是一道經典的陣列操作題目。情境描述：Mr.true 參加面試，因為表現優異獲得特權，可以插隊到指定位置。我們需要模擬這個過程，將新元素插入現有序列的特定位置。

輸入格式

• 第一行：測試案例數 T
• 每組測試資料包含 3 行：
  • 原隊伍人數 N
  • N 個整數，代表原隊伍面試編號序列
  • 兩個整數 P、Q：P 為 Mr.true 的面試編號，Q 為插入位置（第 Q 個位置，索引從 1 開始）

條件保證：編號不重複，N ≤ 10000

輸出格式

輸出插入後的隊伍面試編號序列，數字間以空格分隔。

範例說明

輸入：
2
3
1 2 3
4 2
4
9 8 2 3
7 1

輸出：
1 4 2 3
7 9 8 2 3

第一組：原序列 [1,2,3]，編號 4 插入第 2 位 → [1,4,2,3]
第二組：原序列 [9,8,2,3]，編號 7 插入第 1 位 → [7,9,8,2,3]

解題思路

這是基本的陣列插入操作。核心步驟：

1. 讀取原序列到陣列
2. 從插入位置 Q-1 開始，將後續元素向後移動一位
3. 在 Q-1 位置放入新編號 P
4. 輸出新序列（長度變為 N+1）

C 語言參考實作

#include <stdio.h>

int main() {
    int T, N, P, Q;
    int arr[10001];  // 足夠容納 N+1 個元素
    
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%d", &arr[i]);
        }
        scanf("%d %d", &P, &Q);
        
        // 從後往前移動元素，騰出位置 Q-1
        for (int i = N; i >= Q; i--) {
            arr[i] = arr[i-1];
        }
        arr[Q-1] = P;  // 插入新元素
        
        // 輸出結果
        for (int i = 0; i <= N; i++) {
            printf("%d", arr[i]);
            if (i < N) printf(" ");
        }
        if (T > 0) printf("\n");
    }
    return 0;
}

關鍵點提醒

• 插入位置 Q 是 1-based 索引，轉換為 0-based 時為 Q-1
• 移動元素時必須從後往前，避免覆蓋數據
• 陣列大小需預留 N+1 空間
• 多組測試資料之間需換行分隔

複雜度分析

• 時間複雜度：O(N) 每測試案例，主要花費在元素移動上
• 空間複雜度：O(N) 陣列儲存

這道題目考察基本的陣列操作與索引轉換，是程式設計入門的重要練習。