LeetCode 解題筆記：3789. Minimum Cost to Acquire Required Items

作者：王一哲
日期：2026年11月11日


LeetCode 題目連結：3789. Minimum Cost to Acquire Required Items

解題想法

中等難度題。題目給 5 個整數，$cost1$ 代表單獨買 1 單位的物品 1 的價格，$cost2$ 代表單獨買 1 單位的物品 2 的價格，$costBoth$ 代表同時買 1 單位的物品 1 及 1 單位的物品 2 的價格，$need1$ 代表物品 1 需要買的數量，$need2$ 代表物品 2 需要買的數量，求買到需要的數量至少需要花多少錢？

這題考數學。先試著一起買 $need1, need2$ 之中最少的數量，假設量值為 $buyBoth$，選擇一起買 $costBoth$ 或分開買 $cost1 + cost2$ 之中比較省錢的方案，將金額加到答案 $ans$，再更新 $need1, need2$，減去已經購買的量 $buyBoth$。接下來買需求 1 剩下的量，如果 $need1 > 0$ 才需要計算，$ans$ 再加上 $costBoth, cost1$ 較低者乘以 $need1$，由於題目只要求最低花費，不需要計算多買的量，不用再更新 $need1$。最後買需求 2 剩下的量，如果 $need2 > 0$ 才需要計算，$ans$ 再加上 $costBoth, cost2$ 較低者乘以 $need2$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 71.58%.

class Solution:
    def minimumCost(self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int) -> int:
        # 先試著一起買，選擇一起買或分開買之中比較省錢的方案
        buyBoth = min(need1, need2)  # 需求 1、2 較小的數字
        ans = min(costBoth, cost1 + cost2) * buyBoth
        # 更新需求量
        need1 -= buyBoth
        need2 -= buyBoth
        
        # 買需求 1 剩下的量
        if need1 > 0:
            ans += min(costBoth, cost1) * need1
        
        # 買需求 2 剩下的量
        if need2 > 0:
            ans += min(costBoth, cost2) * need2
        
        return ans

ZeroJudge 解題筆記：f174.m6a2-蛋糕(Cake)

作者：王一哲
日期：2026年11月11日


ZeroJudge 題目連結：f174.m6a2-蛋糕(Cake)

解題想法

每組測資第一列為兩個整數 $N ~(1 \leq N \leq 10^5)$ 及 $K ~(1 \leq K \leq N)$，代表共有 $N$ 塊蛋糕，最多可以吃連續 $K$ 塊蛋糕。第二列為 $N$ 個整數，分別代表每一塊蛋糕的分數。要找出可以吃到的最高總分。

這題考前綴和及滑動視窗。先讀取每塊蛋糕的分數存入陣列 $psum$，開頭多存一個 0，再轉成前綴和，之前用來計算連續區間和。用雙向佇列 $dq$ 儲存滑動視窗區間索引值，出界的索引值從前端移除，後端加入較小的前綴和索引值，前綴和最小的索引值在 $dq$ 前端。$dq$ 先放入 0，最高分數 $imax = 0$。用一個 for 迴圈測試右端點 $i = 1$ 到 $i = n$，目前的區間為 $i-k+1$ 到 $i$，$dq$ 左端為區間左端前一格 $i-k$。用 while 迴圈移除左端已出界的索引值。如果移除後 $dq$ 有資料，$psum[i] - psum[dq[0]]$ 可能是新的最大值，更新 $imax$。再用一個 while 迴圈，移除 $dq$ 右端大於、等於 $psum[i]$ 的索引值，移除後 $i$ 加入 $dq$ 右端。

Python 程式碼

使用時間約為 90 ms，記憶體約為 18.7 MB，通過測試。

def solve():
    import sys
    from collections import deque

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 塊蛋糕
        k = int(data[ptr + 1])  # 最多吃連續 k 塊蛋糕
        ptr += 2

        # 讀取 n 塊蛋糕的分數，再轉成前綴和
        psum = [0] + list(map(int, data[ptr : ptr + n]))
        ptr += n
        for i in range(1, n+1):
            psum[i] += psum[i-1]
        
        # 用 dq 儲存滑動視窗區間索引值，出界的索引值從前端移除，
        # 後端加入較小的前綴和索引值，前綴和最小的索引值在 dq 前端
        dq = deque([0])  # 先放入 0
        imax = 0  # 最大區間和
        for i in range(1, n+1):  # 測試右端 i = 1 ~ n
            # 區間為 [i-k+1 : i+1]，dq 左端為前一格 i-k，不包含 i+1，移除左端已出界的索引值
            while dq and i - dq[0] > k:
                dq.popleft()
            
            # 計算目前的區間和並更新最高分
            if dq:
                imax = max(imax, psum[i] - psum[dq[0]])

            # 移除 dq 右端大於、等於 psum[i] 的索引值
            while dq and psum[dq[-1]] >= psum[i]:
                dq.pop()

            # i 加入 dq 右端
            dq.append(i)
        
        # 印出結果
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：3693. Climbing Stairs II

作者：王一哲
日期：2026年11月10日


LeetCode 題目連結：3693. Climbing Stairs II

解題想法

中等難度題。題目給一個整數 $n ~(1 \leq n \leq 10^5)$，代表有 $n$ 階樓梯，再給一個從 1 開始編號的陣列 $costs$，$costs[i] ~(1 \leq costs[i] \leq 10^4)$ 代表走到第 $i$ 階樓梯需要的成本。每次可以走 1、2 或 3 階樓梯，如果從第 $i$ 階往上走到第 $j$ 階，總成本分為 $cost[j] + (j - i)^2$，計算走到第 $n$ 階的最低成本。

這題考動態規畫。假設要走到第 $i$ 階，3 個變數 $d1, d2, d3$ 分別代表從第 $i-1, i-2, i-3$ 階走上來的最低累計成本，初始值分別為 $0, inf, inf$。接下來用 for 迴圈跑 $i = 1$ 到 $i = n$，走到第 $i$ 階的最低成本為 $curr = cost[i - 1] + min(d1 + 1, d2 + 4, d3 + 9)$，再更新狀態，$curr$ 給 $d1$，$d1$ 給 $d2$，$d2$ 給 $d3$。跑完 for 迴圈之後，答案在 d1。

Python 程式碼

Runtime: 175 ms, beats 92.45%. Memory: 33.42 MB, beats 50.28%.

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        # 假設走到第 i 階，d1、d2、d3 分別代表從 i-1、i-2、i-3 走到 i 的最低累計成本
        d1, d2, d3 = 0, float('inf'), float('inf')
        
        # 從第 1 格走到第 n 格
        for i in range(1, n + 1):
            # 取從 d1 走 1 格、d2 走 2 格、d3 走 3 格的最低成本
            curr = costs[i - 1] + min(d1 + 1, d2 + 4, d3 + 9)
            # 更新狀態，curr 給 d1，d1 給 d2, d2 給 d3
            d1, d2, d3 = curr, d1, d2
        # 最後答案在 d1
        return d1

ZeroJudge 解題筆記：f171.m5a2-快樂數字(HappyNumber)

作者：王一哲
日期：2026年11月10日


ZeroJudge 題目連結：f171.m5a2-快樂數字(HappyNumber)

解題想法

題目將快樂數字定義為符合以下 3 個條件的數字：

1. 不包含 0
2. 包含數字 1 ~ 9
3. 相鄰的數字最多相差 2

每組測資第一列為整數 $N ~(1 \leq N \leq 10^4)$，代表接下來有 $N$ 次詢問。接下來 $N$ 列每列有兩個整數 $P ~(1 \leq P \leq 10^3)$、$Q ~(1 \leq Q \leq 9)$，代表 $P$ 位數、最後一位數字為 $Q$ 的快樂數字，回傳對應的快樂數字數量並對 $10^9 + 7$ 取餘數。

這題考狀態壓縮及動態規畫。因為數字只有 $1$ ~ $9$，可以用一個整數 $mask ~(1 \leq mask \leq 511)$ 代表數字 $1$ 到 $9$ 的狀態，如果這個 $mask$ 轉成 2 進位制之後第 $i$ 位為 $1$，代表數字 $i+1$ 有出現。由於查詢的筆數很多，可以先建表，開一個 $1001 \times 10$ 的二維陣列 $ans$，$ans[i][j]$ 代表 $i$ 位數、結尾為 $j$ 的快樂數字數量。

用動態規畫填表。定義一個 $9 \times 512$ 的二維陣列 $dp$ 記錄數字數量，$dp[j][mask]$ 代表最後一位為 $j$、狀態為 $mask$ 的數量。先初始化 1 位數的狀況，用一個 for 迴圈跑 $j = 1$ 到 $j = 9$，$dp[j][1 << (j - 1)] = 1$。再用一個 for 迴圈跑 2 到 1000 位數的狀況，每次先開一個 $9 \times 512$ 的二維陣列 $nxt$ 記錄新的狀態，裡面再用 3 層 for 迴圈，由外到內分別跑這個數字可能的結尾 $j = 1$ 到 $j = 9$，前一個數字可能的結尾 $k = 1$ 到 $k = 9$，如果 $|j - k| \leq 2$ 再跑所有可能的 $mask$ 更新 $nxt$，跑完這 3 層之後再將 $nxt$ 存到 $dp$。將這次得到的 $i$ 位數、各種尾數 $j$ 對應的快樂數字數量加到 $ans[i][j]$，快樂數字數量在 $dp[1][511]$ 到 $dp[9][511]$ 之中。

Python 程式碼

使用時間約為 1.5 s，記憶體約為 11.5 MB，通過測試。

def solve():
    import sys
    
    mod = 1000000007  # 取餘數用的質數

    # ans[i][j] 代表 i 位數、結尾為 j 的快樂數字數量
    ans = [[0] * 10 for _ in range(1001)]

    # 預計算 P = 1 ~ 1000 所有的答案
    def precompute():
        # dp[j][mask] 代表結尾為 j，數字 1 ~ 9 出現狀態的 mask 的方法數
        # mask 最大為 0b111111111 = 511
        dp = [[0] * 512 for _ in range(10)]
        
        # 初始化，長度 1，只有 1 個數字 j
        for j in range(1, 10):
            dp[j][1 << (j-1)] = 1
        
        # 更新 P = 2 ~ 1000
        for i in range(2, 1001):
            nxt = [[0] * 512 for _ in range(10)]  # 新的狀態
            
            for j in range(1, 10):  # 可能的結尾 j = 1 ~ 9
                for k in range(1, 10):  # 前一個長度的結尾 k = 1 ~ 9 
                    if abs(j - k) <= 2:  # 相鄰的數字最多差 2
                        for mask in range(512):  # 前一個位數的 mask
                            if dp[k][mask] > 0:  # 有對應的方法數
                                new_mask = mask | (1 << (j-1))  # 加入 j 之後的 mask
                                nxt[j][new_mask] = (nxt[j][new_mask] + dp[k][mask]) % mod
            # 更新 dp 為 nxt，跑下一個長度
            dp = nxt

            # 更新 ans[i][j] 為 dp[j][511]，mask = 511 = 0b111111111 代表有 1 ~ 9 所有的數字
            for j in range(1, 10):
                ans[i][j] = dp[j][511]
    # End of precompute，呼叫 precompute 計算答案
    precompute()
    
    # 讀取測資後查表找答案
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 次詢問
        ptr += 1
        for _ in range(n):
            p = int(data[ptr])
            q = int(data[ptr + 1])
            ptr += 2
            result.append(f"{ans[p][q]:d}\n")
    
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：c520.5. 寶島老闆

作者：王一哲
日期：2026年11月9日


ZeroJudge 題目連結：c520.5. 寶島老闆

解題想法

測資第一列為兩個整數 $H, W$，代表地圖的尺寸為 $H \times W$。接下來 $H$ 列，每列為長度 $W$ 的字串，字串中只有代表空地的 . 及代表障礙物的 #。下一列為整數 $N$，代表接下來有 $N$ 天，每天設立一座工廠。最後有 $N$ 列，每列兩個整數 $a, b$，代表這一天工廠設立在坐標 $(a, b)$，坐標由 1 開始編號。工廠發出的汙染物每天會向右、下、左、上的空地擴散一格，輸出每一天結束時被汙染格子的數量。

這類向四周擴散的題目很適合用 BFS 解題，不過這題的陷阱很多，例如工廠設立的位置可能已經被汙染，已經有汙染物從這格向四周擴散，不需要加上這座工廠。可能設在相同的位置重複設立工廠，這也是無效的操作。障礙物可能包圍某一塊區域，汙染物被完全擋位。不過最麻煩的一點在於需要輸出每一天結束時被汙染格子數量，在 BFS 的過程需要很小心。待走訪佇列 $que$ 之中加入目前被汙染的格子坐標。用一個 for 迴圈跑 $n$ 天，先計算當時 $que$ 的長度 $m$，跑完 $que$ 前 $m$ 項時，代表已經檢查完在這一天之中會擴散的格子，這時再加試著加入新設立的工廠坐標，如果這格已經被汙染就不需要加入 $que$，如果有加入 $que$ 則答案 $ans$ 要跟著加 1。

Python 程式碼

程式碼的邏輯是對的，但是速度太慢，只能通過 58% 的測資。

def solve():
    import sys
    from collections import deque
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield part

    tokens = get_tokens()
    result = []

    while True:
        try:
            h = int(next(tokens))
        except StopIteration:
            break
        
        # 地圖尺寸 h*w，轉成二維 list 才能修改字元
        w = int(next(tokens))
        grid = [list(next(tokens)) for _ in range(h)]
        
        # 讀取 n 間工廠的位置，並改成 0-index
        n = int(next(tokens))
        factory = [(int(next(tokens)) - 1, int(next(tokens)) - 1) for _ in range(n)]
        
        # 以天為單位 BFS 找答案
        ans = 0
        que = deque()

        for day in range(n):
            # 1. 處理第 day 天的汙染物擴散狀況，第 0 天會跳過這一段
            sz = len(que)
            for _ in range(sz):
                pos = que.popleft()
                r, c = pos // w, pos % w
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < h and 0 <= nc < w and grid[nr][nc] == '.':
                        ans += 1
                        grid[nr][nc] = '@'  # 被汙染的格子標記成 @
                        que.append(nr * w + nc)

            # 2. 試著加入新的工廠，如果這個位置沒被汙染才加入 que 並將 ans 加 1
            y, x = factory[day]
            if grid[y][x] == '.':
                grid[y][x] = '@'  # 被汙染的格子標記成 @
                que.append(y * w + x)
                ans += 1

            # 3. 印出第 day 天結束時的答案
            result.append(f"{ans:d}\n")

    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1606. Find Servers That Handled Most Number of Requests

作者：王一哲
日期：2026年11月9日


LeetCode 題目連結：1606. Find Servers That Handled Most Number of Requests

解題想法

困難題。題目給一個整數 $k ~(1 \leq k \leq 10^5)$，代表有 $k$ 個伺服器，編號為 $0$ 到 $k-1$。再給一個陣列 $arrival$，$arrival[i]$ 代表任務 $i$ 送給伺服器的時刻。另一個陣列 $load$，$load[i]$ 代表任務 $i$ 需要在伺服器上工作的時間。指派第 $i$ 個任務給伺服器的原則如下：

1. 如果伺服器 $j = i \pmod k$ 有空，將任務指派給伺服器 $j$。
2. 如果伺服器 $j$ 工作中，依序往下找伺服器 $j+1, j+2, \dots$，將任務指派給第一個有空的伺服器。
3. 如果所有伺服器都在工作中，放棄這個任務。

要找出所有的伺服器當中，哪些編號的伺服器被指派最多任務，回傳這些伺服器的編號。

我的寫法是用 3 個最小優先佇列儲存伺服器資料，$ftime$ 記錄每個伺服器最快可用的時刻，內容為 $(time, index)$；$back$ 記錄編號在這次被指派任務的伺服器 $j$ 後面的伺服器；$front$ 記錄編號在這次被指派任務的伺服器 $j$ 前面的伺服器。開一個長度為 $k$ 的陣列 $cnt$ 記錄每個伺服器被指派的任務數量。依序讀取任務送出的時刻 $t$ 及編號 $i$，計算 $j = i \pmod k$，如果 $j = 0$，$front, back$ 的內容要交換。接下來用 whlie 迴圈，從 $ftime$ 前方找可用的伺服器，檢查編號 $s$，如果 $s \geq j$ 放入 $front$，反之放入 $back$。再來決定真正被指派任務的伺服器編號 $p$，如果 $front$ 有資料，$p$ 等於 $front$ 最小的項目；如果 $front$ 是空的，再找 $back$ 之中最小的項目；如果兩者都是空的，放棄這個任務。如果有找到 $p$，將 $cnt[p]$ 加 1，$(t + load[i], p)$ 加入 $ftime$。

Python 程式碼

Runtime: 250 ms, beats 92.23%. Memory: 45.78 MB, beats 50.68%.

class Solution:
    def busiestServers(self, k: int, arrival: list[int], load: list[int]) -> list[int]:
        cnt = [0] * k  # 每個伺服器的工作數量
        
        # priority queue，每個伺服器最快可用的時刻，內容為 (time, index)，先放入不可能的值 */
        ftime = [(1000000001, -1)]
        
        # 目前可用的伺服器，往前找（編號大）為 front，往後找（編號小）為 back */
        back, front = list(range(k)), []
        
        # 主要的解題過程
        n = len(arrival)
        for i in range(n):  # 依序讀取工作索引值 i、派送時刻 t
            t = arrival[i]
            j = i % k  # 理論上要用的伺服器編號 j
            if j == 0:  # j 等於 0，交換 front, back
                front, back = back, front

            while ftime and ftime[0][0] <= t:  # ftime 前方找可用的伺服器，還要檢查編號
                s = heapq.heappop(ftime)[1]  # 取出可用的的伺服器編號 s
                if s >= j:  # 如果 s 大於等於 j，加入 front
                    heapq.heappush(front, s)
                else:  # 如果 s 小於 j，加入 back
                    heapq.heappush(back, s)
            
            p = -1  # 真正要用的伺服器編號
            if front:  # 如果 front 有內容，取出最小值存到 p，移除最小值
                p = heapq.heappop(front)
            elif back:  # 如果 front 沒有內容，back 有內容，取出最小值存到 p，移除最小值
                p = heapq.heappop(back)
            else:  # 如果沒有可用的伺服器，放棄這個工作，執行下一次
                continue
            
            cnt[p] += 1  # 編號 p 的伺服器工作數加 1
            
            heapq.heappush(ftime, (t + load[i], p))  # 將伺服器 p 及下一個可用時刻加入 ftime
        
        # 準備要回傳的答案
        imax = max(cnt)  # 所有伺服器中最多的工作數量
        ans = [i for i in range(k) if cnt[i] == imax]   # 將等於 imax 的伺服器編號加入 ans
        return ans

ZeroJudge 解題筆記：p932.大魔導士 (Archmage)

作者：王一哲
日期：2026年11月8日


ZeroJudge 題目連結：p932.大魔導士 (Archmage)

題目 pdf 檔連結：大魔導士 (Archmage)

解題想法

每組測資只有一列 3 個整數，$K ~(1 \leq K \leq 100)$，$M ~(0 \leq M \leq 1000)$，$N ~(1 \leq N \leq 100)$，分別代表有 $K$ 點技能點數，原來的魔力上限為 $M$，原來的魔法攻擊力為 $N$。使用一點技能點數可以提升 10 點魔力上限，或是提升 3 點魔法攻擊力。每次攻擊會消耗 4 點魔力，每攻擊 3 次可以恢復 3 點魔力。找出可以造成的總傷害最高的技能點數配置方式，答案為一列 3 個整數，分別為分配給提升魔法攻擊力的點數、分配給提升魔力上限的點數、最高傷害，如果有多組解，輸出分配給提升魔法攻擊力點數最少的組合。

由於這題的 $K$ 最大只有 100，可以用一個 for 迴圈測試使用 $0$ 到 $100$ 點提升魔法攻擊力之後的總傷害，找出總傷害最大的組合。

Python 程式碼

使用時間約為 19 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    # 輸入魔力上限、魔法攻擊力，計算最大傷害
    def calc(mp, att):
        damage = 0  # 總傷害
        turn = 0  # 攻擊回數，每 3 次回復 3 點 mp
        while mp >= 4:  # mp 大於、等於 4，繼續攻擊
            turn += 1  # 攻擊回數
            damage += att  # 更新總傷害
            mp -= 4  # 用掉 4 點 mp
            if turn == 3:  # 攻擊 3 次，回復 3 點 mp
                mp += 3
                turn = 0
        return damage
    
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        K = int(data[ptr])  # 技能點數
        M = int(data[ptr + 1])  # 原本的魔力上限
        N = int(data[ptr + 2])  # 原本的魔法攻擊傷害
        ptr += 3
        # 測試點數分配狀況，分配給魔法攻擊傷害 0 ~ K 點，找最大傷害
        a, b, imax = 0, 0, 0  # 答案，分配給魔法攻擊傷害 a 點、魔力上限 b 點，最大傷害 imax
        for i in range(K+1):
            d = calc(M + 10 * (K-i), N + 3*i)
            if d > imax:
                imax = d
                a = i
                b = K-i

        result.append(f"{a:d} {b:d} {imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1267. Count Servers that Communicate

作者：王一哲
日期：2026年11月8日


LeetCode 題目連結：1267. Count Servers that Communicate

解題想法

中等難度題。題目給一個長度 $m \times n$ 的二維陣列 $grid$，如果 $grid[i][j] = 1$ 代表在坐標 $(i, j)$ 有個伺服器，$0$ 代表沒有伺服器。如果同一列或同一欄有 $2$ 部以上的伺服器，這些伺服器可以相連。題目要計算陣列中總共有幾部伺服器相連。

我的寫法很直接，跑 2 次雙層迴圈掃過每一格，第一次計算同一列、同一欄有幾部伺服器並存入陣列 $row, col$，第二次檢查每一格所在的列或欄，如果有 2 部以上的伺服器則答案 $ans + 1$。

Python 程式碼

Runtime: 17 ms, beats 61.30%. Memory: 21.74 MB, beats 16.95%.

class Solution:
    def countServers(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 1. 計算同一列、同一欄有幾部伺服器
        row = [0] * m
        col = [0] * n
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    row[r] += 1
                    col[c] += 1
                    
        # 2. 掃過每一格，如果這格所在的列或欄有 2 部以上的電腦才加到 ans
        ans = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1 and (row[r] >= 2 or col[c] >= 2):
                    ans += 1
        
        return ans

ZeroJudge 解題筆記：s111.C. Bitonic Path

作者：王一哲
日期：2026年11月7日


ZeroJudge 題目連結：s111.C. Bitonic Path

解題想法

題目給一個整數 $n ~(2 \leq n \leq 2000)$，代表共有 $n$ 個點，編號為 $1$ 到 $n$。接下來 $n$ 列，每列有兩個整數 $x_i, y_i ~(-10000 \leq x_i, y_i \leq 10000)$，代表第 $i$ 個點的坐標，測資保證這些坐標依照 $x$ 由小到大排序。要找出一條路徑長最短的路徑，且從節點 $1$ 走到節點 $n$ 時 $x$ 坐標遞增，從節點 $n$ 走回節點 $1$ 時 $x$ 坐標遞減，除了節點 $1$ 以外，其它節點只能走到一次。

由於這題的 $n$ 很大，需要用二維 DP 才不會超時。題目雖然看起來是要來回各走一趟，實際上就是要找到兩點從節點 $1$ 走到節點 $n$ 且中途節點不重複的路徑，並使路徑長最短。以下解題時將節點編號改成 $0$ 到 $n-1$。將節點坐標存到 $pos$ 之中。我們可以假想有兩個人從節點 $0$ 出發，速度較快的人停留在節點 $i$，速度較慢的人停留在節點 $j$，且 $i > j$，這樣兩個人走的路徑中途的節就不會重複。定義一個 $n \times n$ 的二維陣列 $dp$，$dp[i][j]$ 代表速度較快的人停留在節點 $i$，速度較慢的人停留在節點 $j$ 時，對應的最短路徑長，初始值皆設為超出題目上限的值。並初始化為 $dp[0][0] = 0$，因為第一步一定是較快的人從節點 $0$ 走到 $1$，因此 $dp[1][0] = dist(pos[1] - pos[0])$。

接下來用雙層 for 迴圈更新 $dp$。外層迴圈測試較快的人停留在節點 $i = 1$ 到 $i = n-2$，內層迴圈測試較慢的人停留在節點 $j = 0$ 到 $j = i-1$。更新時有兩種可能性：

1. 快的人從 $i$ 走到 $i+1$，慢的人待在 $j$。
2. 慢的人從 $j$ 走到 $i+1$，快、慢交換，慢的待在 $i$。

跑完雙層迴圈之後，快的人已經走到 $n-1$，慢的人從 $j$ 走到 $n-1$。再用一個 for 迴圈，更新 $j = 0$ 到 $j = n-1$，$dp[n-1][n-1]$ 對應的最短路徑長。最後答案會在 $dp[n-1][n-1]$。

Python 程式碼

Python 寫 2 維 DP 還是會超時，需要壓扁成 1 維 DP。

def solve():
    import sys
    from math import hypot  # 計算兩點距離

    def dist(a, b):
        return hypot(a[0] - b[0], a[1] - b[1])

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個點
        ptr += 1
        # 讀取 n 個點的坐標，測資已經依照 x 由小到大排序
        pos = []
        for _ in range(n):
            x = int(data[ptr])
            y = int(data[ptr + 1])
            ptr += 2
            pos.append((x, y))
        
        # 用 2維 DP 找最短路徑長，dp[i][j] 代表快的人在 i、慢的人在 j 的最短路徑長，預設為無窮大
        dp = [[float('inf')] * n for _ in range(n)]
        dp[0][0] = 0  # 起點
        dp[1][0] = dist(pos[1], pos[0])
        for i in range(1, n-1):
            for j in range(0, i):
                # 狀況1，快的人從 i 走到 i+1，慢的人待在 j
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + dist(pos[i+1], pos[i]))
                # 狀況2，慢的人從 j 走到 i+1，快、慢交換，慢的待在 i
                dp[i+1][i] = min(dp[i+1][i], dp[i][j] + dist(pos[i+1], pos[j]))
        # 快的人已經走到 n-1，慢的人從 j 走到 n-1
        for j in range(n):
            dp[n-1][n-1] = min(dp[n-1][n-1], dp[n-1][j] + dist(pos[n-1], pos[j]))
        # 印出結果
        result.append(f"{dp[n-1][n-1]:.2f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1882. Process Tasks Using Servers

作者：王一哲
日期：2026年11月7日


LeetCode 題目連結：1882. Process Tasks Using Servers

解題想法

中等難度題。題目給一個長度為 $n$ 的陣列 $servers$，代表有 $n$ 個伺服器，$server[i]$ 代表第 $i$ 個伺服器的權重。再給一個長度為 $m$ 的陣列 $tasks$，代表有 $m$ 項任務，$tasks[i]$ 代表在時刻第 $i$ 秒送出的任務需要的工作時間。每次送出任務時，將任務派給目前可用的伺服器當中權重最低者，如果伺服器在時刻 $t$ 接收到任務，則這個伺服器下次可用的時刻為目前的時刻加上任務所需時間，即 $t + task$。如果同時有多個權重最低的可用伺服器，任務會派給這些伺服器之中編號較小者。回傳每個任務使用的伺服器編號。

我用最小優先佇列處理這題。$free$ 記錄可用的伺服器，資料為 (權重, 索引值, 可用時刻)，其中可用時刻會超過 int 上限，要用 long 儲存才不會溢位。$working$ 記錄工作中的伺服器，資料為 (可用時刻, 權重, 索引值)。接下來用一個 for 迴圈依序讀取時刻 $i$ 的任務 $tasks[i]$，接下來主要分為 4 個步驟：

1. 先將時刻 $i$ 任務已經完成的伺服器從 $working$ 放回 $free$
2. 如果沒有可用的伺服器，取出 $working$ 之中最早可用的伺服器放入 $free$。
3. 取出可用的伺服器當中權重最低的，這個伺服器的編號 $idx$ 就是任務 $i$ 對應的答案。
4. 伺服器 $idx$ 下次可用的時刻為 $(i, t)$ 較大者加上任務需要的時間 $tasks[i]$，放入 $working$。

不過這個寫法應該還可以再加速。

Python 程式碼

Runtime: 639 ms, beats 36.88%. Memory: 66.06 MB, beats 22.94%.

class Solution:
    def assignTasks(self, servers: list[int], tasks: list[int]) -> list[int]:
        n, m = len(servers), len(tasks)  # 伺服器數量，任務數量
        
        # 最小優先佇列，可用的伺服器 (權重, 索引值, 可用時刻)
        free = [(w, idx, 0) for idx, w, in enumerate(servers)]
        heapq.heapify(free)
        
        # 最小優先佇列，工作中的伺服器 (可用時刻, 權重, 索引值)
        working = []

        # 每個任務分別使用哪一個伺服器
        ans = [-1] * m
        for i, task in enumerate(tasks):
            # 先將時刻 i 任務已經完成的伺服器從 working 放回 free
            while working and working[0][0] <= i:
                u, v, j = heapq.heappop(working)  # (可用時刻, 權重, 索引值)
                heapq.heappush(free, (v, j, u))
            
            # 如果沒有可用的伺服器，取出 working 之中最早可用的伺服器
            if not free:
                u, v, j = heapq.heappop(working)  # (可用時刻, 權重, 索引值)
                heapq.heappush(free, (v, j, u))
            
            # 取出可用的伺服器當中權重最低的
            w, idx, t = heapq.heappop(free)  
            ans[i] = idx  # 任務 i 使用伺服器 idx
            
            # 伺服器 idx 下次可用的時刻為 (i, t) 較大者加上任務需要的時間 task
            heapq.heappush(working, (max(i, t) + task, w, idx))
        
        return ans