NK2MFS Spoj – Lập lịch trên hai máy

Nguồn đề bài: http://vn.spoj.com/problems/NK2MFS/

1. Đề bài NK2MFS Spoj

Có N chi tiết máy cần được gia công lần lượt trên hai máy A và B. Thời gian gia công chi tiết i trên máy A là a_i, thời gian gia công trên máy B là b_i.

Yêu cầu: hãy tìm trình tự gia công các chi tiết trên hai máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất có thể.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10000).
• Dòng thứ hai chứa N số nguyên dương a₁, a₂… a_n (1 ≤ a_i ≤ 10000)
• Dòng thứ ba chứa N số nguyên dương b₁, b₂,… b_n (1 ≤ b_i ≤ 10000).

Kết quả

• Dòng đầu tiên chứa số nguyên dương T là thời điểm sớm nhất có thể hoàn thành.
• Dòng thứa hai chứa N số nguyên cho biết lịch trình gia công các chi tiết máy.

Ví dụ

Input:

3

2 3 1

1 2 3

Output:

7

3 2 1

2. Gợi ý NK2MFS Spoj – Lập lịch trên hai máy

– Thật ra đây là bài TWO phiên bản OI thôi. Các bạn xài Jonhson thì AC