想像一下…

一年一度的動漫展要開賣門票了!主辦單位開放 n 個售票口,每個窗口前都排著一條人龍。你是負責記錄的工作人員:不時有人加入某個窗口的隊尾,也不時有隊伍最尾端的人嫌隊太長、跳去別的窗口重排。所有變動結束後,你要回報每個窗口由隊首到隊尾的完整名單。

用上冊的陣列存這些隊伍,馬上撞牆。陣列的大小在宣告那一刻就得寫死(上冊 6.1 還特別強調:要用 const 常數),但每條隊伍最後會有多長,事先沒有人知道——極端情況下,所有人都擠在同一個窗口。窗口數和總人數都可能到 10^5,每條隊伍都按上限「開好開滿」(上冊 6.1 的慣例),就是 10^5 \times 10^5 = 10^{10} 格的二維陣列、約 40 GB 記憶體,根本開不出來;開小一點,人一多就越界(上冊 6.8 的 UB)。就算記憶體無限大,你還得替每一條隊伍自己記「現在排了幾個人」,加人、走人、跳隊全靠手動加減和搬值,錯一步整份紀錄就亂了。

登入後即可閱讀完整內容

語法書免費開放給所有 AACPOJ 帳號,註冊只要一分鐘。