題目描述:
有 n 隻怪物正朝城市移動。dist[i] 是第 i 隻怪物的初始距離,speed[i] 是其速度。你有一把武器,在時間 0 可以消滅一隻怪物,之後每過 1 分鐘可以再消滅一隻。怪物到達城市(距離 <= 0)時遊戲結束。求最多能消滅多少隻怪物。
解題思路: 貪心策略:優先消滅最快到達城市的怪物。
arrival[i] = ceil(dist[i] / speed[i])。arrival[i] <= i,表示第 i 隻怪物已經到達,遊戲結束。時間複雜度:O(n log n) — 計算到達時間 O(n) + 排序 O(n log n)。
空間複雜度:O(n) — 到達時間陣列。
1. For each monster i: a. arrival[i] = ceil(dist[i] / speed[i]) 2. Sort arrival in ascending order 3. For i from 0 to n-1: a. If arrival[i] <= i: return i (monster arrived before we could shoot) 4. Return n (all monsters eliminated)
計數排序 O(n + T):若到達時間的值域不大(T = max arrival),可以用計數排序替代比較排序。對到達時間計數,然後依序檢查累計量。嚴格 O(n) 但需要額外空間。
優先佇列模擬 O(n log n):用最小堆模擬逐分鐘射擊過程,每分鐘取出到達時間最早的怪物。功能等價但程式碼更複雜。