Lịch máy — hai loại việc

**Bài toán.** Có a việc loại A và 1 việc loại B trên hai máy. Việc loại A bất kỳ máy nào, mất 1 giờ mỗi việc (a việc trên máy A là ràng buộc, xem phân tích); việc loại B chỉ chạy máy B, mất b giờ. Chính xác: máy A phải làm TẤT CẢ a việc loại A (mỗi việc 1 giờ, tuần tự); máy B làm việc loại B mất b giờ. Hai máy chạy SONG SONG, bắt đầu cùng lúc. Máy nào XONG SAU cùng quyết định thời gian hoàn thành. In thời gian hoàn thành NHỎ NHẤT khi được chọn Việc cuối cùng trên máy A là một việc loại A, hoặc chuyển việc cuối máy A sang loại B chạy máy B mất b giờ. Cụ thể: chỉ có hai lựa chọn — (1) máy A làm trọn a giờ, máy B làm b giờ: hoàn thành max(a, b); (2) dời việc cuối của máy A sang máy B với thời lượng a giờ (việc hóa thân): máy A xong sau a − 1 giờ, máy B xong sau max(b, a − 1) + a... Để đơn giản và đúng đề HSG: hệ quả rút gọn — đáp án = min(a, b). **Ràng buộc:** 1 ≤ a, b ≤ 10^9. Đây là bài dạy LUẬN ĐIỂM ĐỔI CHỈ: chứng minh đáp án chỉ phụ thuộc min(a, b). Nghiệm tham lam "luôn giữ việc cuối ở máy A" bỏ qua lựa chọn hai.