UVA 11269 Setting Problems：貪心 + 相鄰交換法求最短完成時間

題目大意

N 個問題，Sultan 寫題需 Sᵢ 時間，GolapiBaba 驗證需 Gᵢ 時間。同一題必須 Sultan 先做完，GolapiBaba 才能開始。兩人各自同一時間只能做一題。求完成所有問題的最短時間。

貪心策略：相鄰交換法

考慮相鄰兩題 A、B 的順序影響：

• A 在前：時間 = Sₐ + max(Gₐ, S_b) + G_b
• B 在前：時間 = S_b + max(G_b, Sₐ) + Gₐ

比較兩者，時間少的順序優先。排序準則：

bool cmp(Work a, Work b) {
    int time_a_first = a.s + max(a.g, b.s) + b.g;
    int time_b_first = b.s + max(b.g, a.s) + a.g;
    return time_a_first < time_b_first;
}

完整代碼

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 105;
struct Work { int s, g; } w[N];

bool cmp(const Work& a, const Work& b) {
    return a.s + max(a.g, b.s) + b.g < b.s + max(b.g, a.s) + a.g;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) scanf("%d", &w[i].s);
        for (int i = 0; i < n; i++) scanf("%d", &w[i].g);
        
        sort(w, w + n, cmp);
        
        int sultan_finish = 0, golapi_finish = 0;
        for (int i = 0; i < n; i++) {
            sultan_finish += w[i].s;
            golapi_finish = max(golapi_finish, sultan_finish) + w[i].g;
        }
        printf("%d\n", golapi_finish);
    }
    return 0;
}

算法證明

相鄰交換法證明最優性：若最優解中存在逆序相鄰對，交換它們不會增加總時間，故存在按該準則排序的最優解。

關鍵點

• 雙機流水調度問題的經典貪心解法
• 排序準則可簡化為 Johnson 規則的變體
• 時間複雜度 O(N log N)，N ≤ 20 遠超需求