Codeforces 523D：排序與優先隊列模擬銀行排隊

問題描述

有 n 位顧客和 k 個窗口。每位顧客給出到達時間和辦理所需時間。顧客按到達時間先後服務，每個窗口同一時刻只能服務一位。輸出每位顧客離開時間。

解題思路

使用優先隊列（最小堆）維護窗口可用時間。首先將 k 個窗口初始可用時間設為 0。按到達時間排序顧客。依次處理每位顧客：取出堆頂最早可用窗口，其開始服務時間為 max(到達時間, 窗口可用時間)；結束時間 = 開始時間 + 辦理時間；將該窗口新可用時間推回堆。記錄每位顧客的結束時間即為答案。

代碼實現 (Java)

import java.util.*;
public class Solution {
    static class Customer implements Comparable {
        long arrive, process;
        int id;
        Customer(long a, long p, int i) { arrive = a; process = p; id = i; }
        public int compareTo(Customer o) { return Long.compare(arrive, o.arrive); }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        List list = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            list.add(new Customer(in.nextLong(), in.nextLong(), i));
        }
        Collections.sort(list);
        PriorityQueue pq = new PriorityQueue<>();
        for (int i = 0; i < k; ++i) pq.add(0L);
        long[] ans = new long[n + 1];
        for (Customer c : list) {
            long avail = pq.poll();
            long start = Math.max(avail, c.arrive);
            long end = start + c.process;
            ans[c.id] = end;
            pq.add(end);
        }
        for (int i = 1; i <= n; ++i) System.out.println(ans[i]);
    }
}

複雜度分析

• 時間複雜度：O(n log n + n log k)，排序佔主導。
• 空間複雜度：O(n + k)。

總結

經典的多窗口排隊模擬問題，優先隊列完美契合「總是選最早空閒窗口」的貪心策略。注意到達時間可能大於窗口可用時間，需取最大值。