HDU 3661 Assignments 完整解析

N 名工人，每人需分配一個 A 類任務和一個 B 類任務。A 任務耗時 xᵢ，B 任務耗時 yⱼ。標準工時 T，超時部分 t - T 需支付加班費。求最小總加班費。

核心貪心策略：最小與最大配對

將 A 任務按耗時升序排列，B 任務按耗時降序排列，一一配對。證明：若最小 A 與最大 B 配對超時，則該 A 與任意 B 均超時（必須支付）；若不超時，則此配對最優（釋放較小 B 給較大 A，整體最優）。

完整 AC 程式碼

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

const int MAXN = 1100;

int main() {
    int n, T;
    while (scanf("%d %d", &n, &T) == 2) {
        vector A(n), B(n);
        for (int i = 0; i < n; i++) scanf("%d", &A[i]);
        for (int i = 0; i < n; i++) scanf("%d", &B[i]);
        
        sort(A.begin(), A.end());                 // 升序
        sort(B.begin(), B.end(), greater()); // 降序
        
        long long overtime = 0;
        for (int i = 0; i < n; i++) {
            int total = A[i] + B[i];
            if (total > T) overtime += total - T;
        }
        printf("%lld\n", overtime);
    }
    return 0;
}

範例驗證

輸入：
2 5
4 2
3 5

A 排序：2, 4
B 排序：5, 3
配對：2+5=7(超2), 4+3=7(超2) → 總加班費 = 4 ✓

關鍵點總結

• 排序方向相反：一升一降，核心貪心策略
• 加班費計算：max(0, A[i]+B[i] - T)
• 長整型：N≤1000，單任務≤1000，總和 ≤ 2×10⁶，int 足夠，用 long long 更保險
• 多測資輸入：while(scanf(...)==2)