Bài toán qua sông Pasal cần giúp đỡ? (thuật toán hoặc ý tưởng)?

[hcvtpt]

Trong mùa mưa lũ tại các tỉnh miền Trung, có N bạn học sinh cần sang sông để đi học, với phương tiện là một chiếc thuyền tự lái. Chiếc thuyền tự lái này chỉ chở được tối đa là 2 người trên mỗi chuyến đi. Bạn thứ i nếu sang sông một mình sẽ mất thời gian là M[i]. Bạn thứ i và thứ j cùng sang sông sẽ mất thời gian Max(M[i], M[j]). Em hãy lập trình giúp các bạn đó tính thời gian nhỏ nhất có thể để đưa được tất cả các bạn qua sông cho kịp giờ vào lớp.
Ví dụ:
N=7
M: 2 3 5 6 4 10 14
Thời gian nhỏ nhất cần tìm là: 45
Dữ liệu vào:
Dòng 1: Số học sinh N
Dòng 2: Thời gian sang sông của từng bạn M[i], i=1,2,…,N.
Dữ liệu ra:
Dòng 1: Thời gian nhỏ nhất để đưa tất cả các bạn qua sông.
Ví dụ:
Dữ liệu vào:
7
2 3 5 6 4 10 14
Dữ liệu ra:
45

[HGMinh95]

Theo mình bạn cứ sắp xếp mảng M[1..N] tăng dần, duyệt từ cuối lên cứ 2 người gần nhau cho đi một chuyến thì sẽ được thời gian nhỏ nhất.

Dữ liệu vào:
7
2 3 5 6 4 10 14
Dữ liệu ra:
45

Sao lại ra 45???

[hcvtpt]

Theo mình bạn cứ sắp xếp mảng M[1..N] tăng dần, duyệt từ cuối lên cứ 2 người gần nhau cho đi một chuyến thì sẽ được thời gian nhỏ nhất.


Sao lại ra 45???

Mình đã thử nhiều cách nhưng cũng chưa hiểu tại sao ra 45 luôn.
:S

[HGMinh95]

Mình thấy đề bài hình như thiếu thời gian để thuyền quay trở về thì phải.

[hcvtpt]

Mình thấy đề bài hình như thiếu thời gian để thuyền quay trở về thì phải.

đi và về đều là max của người lái thuyền

2 3 sang
2 về
10 14 sang
3 về
2 3 sang
2 về
5 6 sang
3 về
2 3 sang
2 về
2 4 sang

3 + 2 + 14 + 3 + 3 + 2 + 6 + 3 + 3 + 2 + 4 = 45

[HGMinh95]

B1: Đầu tiên, sắp xếp dãy m[1..n] tăng dần
B2: Cho hai người đầu danh sách sang (m[1] và m[2])
B3: Cho người có thời gian nhỏ hơn về (m[1])
B4: Cho 2 người có thời gian sang sông lớn nhất sang
B5: Cho m(2) quay về
B6: Nếu còn người chưa sang sông, quay lại bước 2
Lưu ý: Các bước 3, 4, 5 chỉ thực hiện khi còn người chưa sang sông

[kieutrangnvt]

help me! In ra chữ số thứ N trong phần thập phân của thương số khi chia p cho q.
cho e xin ý tưởng với ạ