HDU 1789 Doing Homework Again - 貪心策略最小化扣分

問題描述

N 份作業 (N ≤ 1000)，每份有截止天數 deadline 和逾期扣分 。每天最多做 1 份作業。安排順序使總扣分最小。輸出最小扣分。

貪心策略：高分優先 + 盡晚安排

1. 按 score 降序排序 (分數相同按 deadline 升序)。
2. 維護布爾數組 used[day] 標記該天是否已安排作業。
3. 對每份作業 (按排序順序)：
   • 從 min(deadline, N) 向前找第一個未用的天。
   • 若找到 (day ≥ 1)，標記該天已用。
   • 若找不到 (day = 0)，無法按時完成，累加扣分。

正確性證明

• 高分作業優先安排，確保大扣分優先避免。
• 盡晚安排 (從 deadline 向前)，為早截止日期的作業留出前方時隙，不阻塞更緊急的任務。
• 若某高分作業無法安排，說明前 deadline 天已被同等或更高分作業佔滿，無解。

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;

struct HW { int deadline, score; } hw[MAXN];
bool used[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &hw[i].deadline);
        for (int i = 0; i < n; i++) scanf("%d", &hw[i].score);
        sort(hw, hw+n, [](const HW& a, const HW& b) {
            return a.score != b.score ? a.score > b.score : a.deadline < b.deadline;
        });
        fill(used, used+n+1, false);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int day = min(hw[i].deadline, n);
            while (day > 0 && used[day]) day--;
            if (day > 0) used[day] = true;
            else ans += hw[i].score;
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 排序 O(N log N)
• 安排循環 O(N²) 最壞 (N=1000 可接受)
• 可用並查集優化「找前一個空閒天」至 O(N α(N))，但非必要。

變體擴展

若作業有耗時 (非單位時間)，則為經典「調度問題」，需用 DP 或優先隊列。本題單位時間貪心最優。