Detailed explanation of classic algorithmic problem of crossing the river

The main content of this article is a detailed explanation of the classic algorithm problem of crossing the river. Interested friends can learn more I hope it helps you.

Description

A group of N people want to cross the river in a boat. This boat can only carry two people at most. So some kind of shuttle arrangement has to be put in place to paddle back and forth so that everyone can get across. Everyone has a different rowing speed; the speed of a pair of runners depends on the speed of the slower person. Your job is to determine a strategy that will minimize the time it takes these people to cross the river.
Input

The first line of input contains an integer T (1<=T<=20), the number of test cases. Next are T cases. The first line of each case contains N, and the second line contains N integers giving the time for each person to cross the river. Each case is preceded by a blank line. There won't be more than 1,000 people, and no one will need more than 100 seconds to cross.
Output

For each test case, print a line containing the total number of seconds it took for all N people to cross the river.
Sample input

1
4
1 2 5 10
Sample output

17

-------------------------------------------------- -------------------------------------------------- --------------------------------

problem analysis
(The speeds of the following N people are represented by abcd..., and are sorted in ascending order of speed)

1. When n= 1, time is a
2. When n= 2, time Then it is b
3. When n= 3, time is a b c (a crosses the river with any person, a comes back, and then crosses the river with the remaining people)
4. When n>= 4, the problem is much more complicated, because if any two people cross the river, there are many situations where one of them comes back after crossing the river. We need to analyze it here
   Observing the question, we can find that there are two most important points in crossing the river.
   Scheme [1] For two people crossing the river, the time spent is determined by the longest person
   In view of this, we can put the slowest d and the second slowest c together, so that the second slowest time c Just ignored.
   Plan [2] The time spent by a person who comes back is determined by him alone
   In view of this, we can let the fastest a send the others one by one, and then let the fastest a take the boat Send it back

   Realize the above solution
   When n = 4 (The speed of N people below is represented by abcd..., and according to the speed Sorting in ascending order) () indicates the time spent
   Scheme [1] abcd
   ab (b) past
   a (a) back
   cd (d) past
   b (b) back
   ab(b) past
   Time spent: a 3b d

   Plan [2] abcd
   ad(d) past
   a(a) back
   ac (c) past
   a (a) back
   ab (b) past
   Time spent : 2a b c d

   Calculation example
   Now we import the question sample {1, 2, 5, 10}
   Plan [1] Time = 17
   Plan [2] Time = 19
   So use plan [1] It takes the shortest time, the time is 17

   But if we modify the data {1, 2, 2, 10}
   Scheme [1] time = 17
   Scheme [2] time = 16
   This time, plan [2] takes the shortest time, with a time of 16;

   If we approximate the time spent by the two plans,
   Plan [1]: 2b
   plan [2]: a c
   It can be seen that the time spentThe decisive factor lies in the fastest a, the second fastest b and the second slowest c. We only need to compare 2b and a c and choose to spend The solution that takes the least time is sufficient.

   When n > 4We can express it as using the first two fastest people to transport the slowest two people, and the number of people will be reduced by 2 after transporting.

   Related tutorials: Java video tutorial

   The following is the AC code, for reference only

   import java.util.Arrays;
   import java.util.Scanner;
   
   public class 过河         
   {
   	static long time = 0L;
   	public static void main(String[] args)
   	{
   		Scanner sc = new Scanner(System.in);
   		int m = sc.nextInt();
   		for (int i = 0; i < m; i++)
   		{
   			int n = sc.nextInt();
   			int[] A = new int[n];
   			for (int j = 0; j < n; j++)
   			{
   				A[j] = sc.nextInt();
   			}
   			Arrays.sort(A);
   			f(A);
   			System.out.println(time);
   			time = 0L;
   		}
   	}
   	public static void f(int[] A) {
   		if(A.length == 3) {
   			time += A[0] + A[1] + A[2];
   			return;
   		}
   		if(A.length == 2) {
   			time += A[1];
   			return;
   		}
   		if(A.length == 1) {
   			time += A[0];
   			return;
   		}
   		if(A[0] + A[A.length - 2] < A[1] * 2) {
   			time += 2 * A[0] + A[A.length - 2] + A[A.length - 1];
   		}else {
   			time += A[0] + 2 * A[1] + A[A.length - 1];
   		}
   		int[] B = Arrays.copyOfRange(A, 0, A.length - 2);
   		f(B);
   	}
   }

   The above is the detailed content of Detailed explanation of classic algorithmic problem of crossing the river. For more information, please follow other related articles on the PHP Chinese website!