Bridge Crossing
InterviewTime limit1sMemory limit128 MB
Given n people's crossing times and one flashlight, find the minimum total time to move everyone across when at most two cross together.
- Level
Medium6 of 10
- Topics
- Greedy, Sorting, Dynamic programming, Implementation
- Solved
- No attempts yet
Problem
n people want to cross a bridge at night. At most two people may cross at a time, and every crossing group must carry a flashlight. There is only one flashlight among the n people, so after a group crosses, someone must carry the flashlight back so that the remaining people can cross.
Each person may cross at a different speed. When two people cross together, the group takes as long as the slower of the two. Determine the minimum total time needed for all n people to cross the bridge.
Input
The first line contains the number of people n. Each of the next n lines contains one crossing time.
There are at most 1000 people, and no one takes more than 100 seconds to cross the bridge.
Output
Print a single integer: the minimum number of seconds required for all n people to cross the bridge.