HDU 2019 題解：有序序列插入元素保持有序（C 語言實現）

HDU 2019 - 有序數組插入新元素

題目大意： 已有 n (n≤100) 個按升序排列的整數，再給一個整數 x，將 x 插入序列使其保持有序。多組測試，n=m=0 結束。

算法思路

1. 讀入 n、m，若均為 0 退出。
2. 讀入 n 個有序整數存入數組 `a[0..n-1]`。
3. 從右向左掃描，將大於 m 的元素右移一位，直到找到 `a[i] <= m` 的位置，將 m 放入 `a[i+1]`。
   (等價於 `std::upper_bound` 位置插入，保持穩定性)
4. 輸出 n+1 個元素，空格分隔。

AC 代碼

#include 

int main() {
    int n, m, a[101]; // n+1 防越界
    while (scanf("%d %d", &n, &m) == 2) {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        int i = n - 1;
        while (i >= 0 && a[i] > m) {
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = m; // 插入位置

        for (int j = 0; j <= n; j++) {
            if (j) printf(" ");
            printf("%d", a[j]);
        }
        printf("\n");
    }
    return 0;
}

關鍵點提示

• 數組大小開 `101` 防止插入後越界。
• 插入邏輯等價於**二分查找上界**後移動元素，但 n≤100 線性掃描足夠簡單高效。
• 條件 `a[i] > m` 而非 `>=`，保證相等元素插在現有同值元素**之後**（穩定插入）。
• 輸出格式：`n+1` 個數，空格分隔，行末換行。

測試樣例

輸入：
3 3
1 2 4
0 0

輸出：
1 2 3 4

擴展：二分查找插入位置 (O(log n))

int pos = 0, left = 0, right = n - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    if (a[mid] <= m) pos = mid + 1, left = mid + 1;
    else right = mid - 1;
}
// pos 為插入位置，然後移動元素 a[pos...n-1] 右移