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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

1. Đề bài TWO Spoj

Có N chi tiết máy cần được gia công lần lượt trên 2 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]. Hãy tìm trình tự gia công các chi tiết trên 2 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ể.

Input

  • Dòng 1: số nguyên dương N (1 ≤ N ≤ 10000).
  • Dòng 2: N số nguyên dương a[1], …, a[n]. (1 ≤ a[i] ≤ 10000)
  • Dòng 3: N số nguyên dương b[1], …, b[n]. (1 ≤ b[i] ≤ 10000)

Output

  • Dòng 1: Số nguyên dương T là thời điểm sớm nhất có thể hoàn thành.
  • Dòng 2: N số nguyên là lịch trình gia công các chi tiết máy.

Example

Input:

3

2 3 1

1 2 3

Output:

7

3 2 1

2. Gợi ý TWO Spoj

– Các bạn dùng thuật toán Jonhson ^^

3. Code Tham Khảo TWO Spoj

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *