用模擬精靈腳本解百度編程大賽兩道經典題：連續正整數和與最大重疊區間

工具介紹

「模擬精靈」是一款國產鍵鼠腳本工具，語法類 Pascal/Lua 混合，支持變量、循環、函數、文件操作，適合快速原型驗證算法邏輯。本文用它解決百度編程大賽兩道題目。

題目一：連續正整數和 (10分)

問題描述

輸入一個正整數 N，找出所有長度 ≥2 的連續正整數序列，使其和等於 N。輸出按起始數遞增排序，格式如 15 = 1 + 2 + 3 + 4 + 5。無解輸出 NONE。

算法思路

雙重循環枚舉起始數 i (1 ~ N/2)，內層累加 j 直到和 ≥ N。若等於 N 輸出序列。時間複雜度 O(N²/4)，對 N ≤ 10⁶ 尚可接受。

模擬精靈實現

print("請輸入一個正整數:")
ns = io.read()
while (not tonumber(ns)) do
    print("請輸入有效整數")
    ns = io.read()
end
n = tonumber(ns)

found = false
for i = 1, n/2 + 1 do
    local sum = 0
    local last = 0
    for j = i, n/2 + 1 do
        sum = sum + j
        last = j
        if sum == n then break end
        if sum > n then break end
    end
    if sum == n then
        found = true
        local out = n .. " = " .. i
        for y = i+1, last do out = out .. " + " .. y end
        print(out)
    end
end
if not found then print("NONE") end

題目二：最大重疊區間大小 (20分)

問題描述

讀取 input.txt，每行兩個正整數 A B (順序隨機) 表示區間 [min(A,B), max(A,B)]。求任意兩行區間重疊部分的整數個數的最大值。行數高達 1,000,000，內存限制 256MB，需 O(N log N) 或 O(N) 算法。

優化算法：掃描線 + 差分數組 / 排序端點

1. 讀取所有區間，統一為 [L, R] (L ≤ R)。
2. 將所有端點事件 (L, +1), (R+1, -1) 收集並排序。
3. 掃描累加計數，記錄最大值。重疊區間大小 = 最大計數 ≥ 2 時的連續段長度？
   修正：題目定義「重疊區間大小」為「同時屬於行 i 和行 j 的整數個數」，即任意兩區間交集長度的最大值。
   正確做法：對所有區間按左端點排序，維護當前遇到的最大右端點 maxR。遍歷時，若當前區間左端點 L ≤ maxR，則交集長度 = min(R, maxR) - L + 1，更新答案；並更新 maxR = max(maxR, R)。O(N log N) 排序，O(1) 額外空間。

模擬精靈代碼 (含測試數據內嵌)

-- 測試數據
txt = [[
12 20
20 32
1 25
6 7
11 5
6 4
6 8
1 3
2 23
11 22
1 32
4 18
]]

-- 解析
tab = string.split(txt, "\n")
for k, v in pairs(tab) do
    local t = string.split(v, " ")
    tab[k] = {math.min(tonumber(t[1]), tonumber(t[2])), math.max(tonumber(t[1]), tonumber(t[2]))}
end

-- 排序
table.sort(tab, function(a,b) return a[1] < b[1] end)

maxOverlap = 0
maxR = tab[1][2]
for i = 2, #tab do
    local L = tab[i][1]
    local R = tab[i][2]
    if L <= maxR then
        local overlap = math.min(R, maxR) - L + 1
        if overlap > maxOverlap then maxOverlap = overlap end
    end
    if R > maxR then maxR = R end
end

print("最大重疊區間大小: " .. maxOverlap)

性能與內存分析

• 題目一：N=10⁹ 時 O(N²) 會超時，可用數學公式 N = k*(2a+k-1)/2 枚舉長度 k 求起始 a，降至 O(√N)。
• 題目二：排序 100 萬行約需 1-2 秒，內存約 16MB (存結構體)，遠低於 256MB 限制。若需更快，可用基數排序 O(N) 或外部排序。

總結

模擬精靈雖非主流開發語言，但其動態類型、內建高階函數、交互式運行特性，非常適合算法競賽的快速驗證階段。實際提交時需移植至 C++/Java 並優化邊界情況。