Một nhà máy nhận được đơn đặt hàng cho sản phẩm. sản phẩm này lần lượt được gia công tại hai phân xưởng A và B, và bắt buộc phải được gia công tại phân xưởng A trước rồi mới được chuyển sang phân xưởng B.
Thời gian gia công sản phẩm tại phân xưởng A và B lần lượt là . Hãy sắp xếp thứ tự gia công cho sản phẩm này sao cho tổng thời gian gia công là ngắn nhất.
Thời gian gia công ở đây được hiểu là: khoảng thời gian từ lúc bắt đầu gia công sản phẩm đầu tiên cho đến khi tất cả các sản phẩm đều đã hoàn thành gia công ở cả hai phân xưởng A và B.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên , biểu thị số lượng sản phẩm.
Dòng tiếp theo chứa số liệu, biểu thị thời gian gia công tại phân xưởng A cho từng sản phẩm.
Dòng cuối cùng chứa số liệu, biểu thị thời gian gia công tại phân xưởng B cho từng sản phẩm.
Kết quả:
Dòng đầu tiên xuất ra một số, là thời gian gia công ít nhất.
Dòng thứ hai xuất ra thứ tự gia công các sản phẩm để đạt được thời gian tối thiểu đó (in ra chỉ số của sản phẩm).
