V10-DE13
Qua cầu
Nộp bàiPoint: 4
Có n (1 <= n <= 10^6) người cần qua cầu trong đêm tối. Cầu rất yếu nên chỉ đi 1 lúc tối đa được 2 người. Họ cần có đèn mới qua được cầu; mà cả nhóm chỉ có duy nhất 1 cái đèn. Vì vậy nên mỗi lần 2 người qua sông thì phải cử 1 người cầm đèn quay trở lại. Mỗi người qua cầu với các tốc độ lần lượt là a[i] giây (1 <= a[i] <= 100). Hai người đi cùng nhau thì sẽ đi theo tốc độ của người đi chậm hơn. Ta cần tìm thời gian ít nhất để tất cả n người qua bên kia cầu.
Input
- Dòng đầu là số nguyên n;
- Dòng thứ 2 chứa n số là thời gian đi qua cầu của n người.
Output
Ghi ra tổng thời gian đi qua cầu.
Ví dụ:
Input
4
1 3 8 12
Output
22
Giải thích:
Trong test 1 đi theo cách như sau:
1) Người 1 và 2 qua cầu: mất 3 giây.
2) Người 1 cầm đèn quay trở lại: mất 1 giây.
3) Người 3 và 4 qua cầu: mất 12 giây.
4) Người 2 cầm đèn quay trở lại: mất 3 giây.
5) Người 1 và 2 qua cầu: mất 3 giây.
Tổng cộng mất 22 giây.
Ví dụ 2:
Input
5
1 3 6 8 12
Output
29
Trong test 2 đi theo cách như sau:
1) Người 1 và 2 qua cầu: mất 3 giây.
2) Người 1 cầm đèn quay trở lại: mất 1 giây.
3) Người 4 và 5 qua cầu: mất 12 giây.
4) Người 2 cầm đèn quay trở lại: mất 3 giây.
5) Người 1 và 3 qua cầu: mất 6 giây.
6) Người 1 cầm đèn quay trở lại: mất 1 giây.
7) Người 1 và 2 qua cầu: mất 3 giây.
Tổng cộng mất 29 giây.
Ví dụ 3:
Input
1
4
Output
4
Người 1 qua cầu mất 4 giây. Tổng cộng mất 4 giây.