HDU 5437 Alisha's Party：優先隊列模擬解題詳解

題目大意

有k人攜帶價值v_i的禮物到達，共開m次門。第i次開門時有t_i人到達，放入p_i人。所有人到達後再開一次門放入剩餘所有人。規則：禮物價值高者優先，價值相同先到先進。q次詢問，輸出第n個進場者的名字。m可為0。

核心思路：優先隊列 + 事件模擬

1. 將所有人按到達時間分組存儲（結構體含id、value、name，id體現到達順序）。
2. 將開門事件按時間排序（結構體a時間、b放入人數）。
3. 維護一個set（或priority_queue）作為候選池，按value降序、id升序排序。
4. 模擬流程：遍歷時間，將到達者加入候選池，遇開門事件從池中取出b人記入答案序列。
5. 最後一次開門處理剩餘所有人。
6. 回答查詢：直接訪問答案數組。

關鍵數據結構

struct Person {
    int id, value;
    char name[220];
    bool operator<(const Person& o) const {
        return value == o.value ? id < o.id : value > o.value; // 大根堆語義
    }
};

struct DoorEvent {
    int time, count;
    bool operator<(const DoorEvent& o) const { return time < o.time; }
};

算法流程圖解

sort(people by arrival time)
sort(events by time)
idx = 0
for each event e:
    while idx < n && people[idx].arrival <= e.time:
        candidate_set.insert(people[idx++])
    repeat e.count times:
        if candidate_set not empty:
            ans.push_back(*candidate_set.begin())
            candidate_set.erase(begin())
// 最終開門
while candidate_set not empty:
    ans.push_back(*candidate_set.begin())
    candidate_set.erase(begin())
// 回答查詢
for each query q:
    print ans[q-1].name

複雜度分析

• 排序：O(n log n + m log m)
• 模擬：每人進出集合各一次，O(n log n)
• 查詢：O(1)
• 總體：O((n+m) log n)，滿足n ≤ 150000約束。

易錯點提醒

• m=0時無開門事件，需直接進入最終開門邏輯。
• 查詢索引可能超出答案長度（題目保證合法，但代碼建議防禦）。
• set迭代器失效：erase(begin())安全，但erase(it++)需謹慎。
• 名稱最大長度220，數組留足餘量。