CF 508C：Anya and Ghosts - 貪心點燭策略

問題描述

m 個幽靈到達時刻 w_i（遞增），蠟燭燃燒 t 秒，點燃需 1 秒。每次幽靈到達需至少 r 支正在燃燒的蠟燭。求最少蠟燭數，或判斷不可能 (-1)。

貪心策略：盡可能晚點燃

倒序處理幽靈（從最後一個到第一個）。對於幽靈 w_i，其有效點燃時間窗口為 [w_i - t, w_i - 1]（點燃後 1 秒開始燃燒，燃燒 t 秒，覆蓋 w_i）。

維護已點燃蠟燭的時間點集合（用隊列或數組）。對當前幽靈，統計窗口內已有蠟燭數 cnt。若 ，需補充 r - cnt 支，選擇窗口內 最晚 的空閒秒點燃（從 w_i - 1 向前）。這樣最大化蠟燭對後續（更早）幽靈的覆蓋。

代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXT = 605; // w_i ≤ 300, t ≤ 300, 可能負時間偏移
int used[MAXT * 2]; // 時間偏移 +300

int main() {
    int m, t, r; scanf("%d%d%d", &m, &t, &r);
    vector w(m);
    for (int &x : w) scanf("%d", &x);
    if (t < r) { puts("-1"); return 0; } // 窗口長度不足

    int ans = 0;
    const int OFF = 300; // 時間偏移，處理負時間
    for (int i = m - 1; i >= 0; --i) {
        int cnt = 0;
        for (int sec = w[i] - t; sec <= w[i] - 1; ++sec)
            if (used[sec + OFF]) ++cnt;
        int need = r - cnt;
        for (int sec = w[i] - 1; need > 0; --sec) {
            if (!used[sec + OFF]) {
                used[sec + OFF] = 1;
                ++ans;
                --need;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

關鍵點

• 時間窗口長度 t 若小於 r 直接無解。
• 倒序貪心保證後點燃的蠟燭盡可能覆蓋更多前面的幽靈。
• 時間範圍 [-300, 600]，偏移數組即可，無需複雜結構。

總結

經典區間覆蓋貪心：倒序處理，盡可能晚放置資源。同類問題：會議室安排、射箭氣球 (LeetCode 452) 等。