강을 건너는 고전적인 알고리즘 문제에 대한 자세한 설명

이 기사의 주요 내용은 강 건너기의 고전적인 알고리즘 문제에 대한 자세한 설명입니다. 관심 있는 친구들이 이에 대해 배울 수 있기를 바랍니다.

Description

N명이 배를 타고 강을 건너고 싶어 합니다. 이 배는 최대 2명만 태울 수 있습니다. 따라서 모든 사람이 건널 수 있도록 앞뒤로 노를 저을 수 있도록 일종의 셔틀 장치를 마련해야 합니다. 사람마다 노를 젓는 속도가 다릅니다. 두 명의 주자의 속도는 느린 사람의 속도에 따라 다릅니다. 당신의 임무는 사람들이 강을 건너는 데 걸리는 시간을 최소화하는 전략을 결정하는 것입니다.
Input

입력의 첫 번째 줄에는 테스트 사례 수인 정수 T(1<=T<=20)가 포함됩니다. 다음은 T케이스입니다. 각 경우의 첫 번째 줄에는 N이 포함되고, 두 번째 줄에는 각 사람이 강을 건너는 데 걸리는 시간을 제공하는 N개의 정수가 포함됩니다. 각 사례 앞에는 빈 줄이 있습니다. 1,000명을 넘지 않을 것이며, 건너는 데 100초 이상이 필요하지 않을 것입니다.
출력

각 테스트 사례에 대해 N명 모두가 강을 건너는 데 걸린 총 시간(초)을 포함하는 줄을 인쇄하세요.
샘플 입력

1
4
1 2 5 10
샘플 출력

17

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

문제 분석
(다음 N명의 속도는 abcd...로 표시되며, 속도의 오름차순으로 정렬됩니다.)

1. n=1일 때 시간은 a
2. n일 때 =2, 시간은 b
3. n=3일 때 시간은 a+b+c입니다(a가 어떤 사람과 함께 강을 건너고, a가 돌아와서 나머지 사람들과 함께 강을 건너갑니다)
4. n>=일 때 4, 문제는 훨씬 더 복잡합니다. 두 사람이 강을 건너면 그 중 한 사람이 강을 건넌 후 다시 돌아오는 상황이 많기 때문입니다. 여기서 분석해야 합니다.
   질문을 살펴보면 강을 건너는 데 가장 중요한 두 가지 포인트
   계획 [1] 건너기 강 위의 두 사람의 소요 시간은 가장 긴 사람에 따라 결정됩니다
   이를 고려하여 가장 느린 d와 두 번째로 느린 c를 합치면, 두 번째로 느린 시간 c는 무시됩니다.
   옵션 [2] 돌아오는 사람의 시간은 그 사람만이 결정한다
   이를 고려하여 가장 빠른 사람이 다른 사람을 하나씩 보내고 가장 빠른 사람이 배를 다시 보낼 수 있습니다

   위의 Scheme을 구현해 보세요
   n = 4일 때(다음 N명의 속도는 abcd로 표시되고... 속도의 오름차순으로 정렬됩니다.) ()는 소요 시간을 나타냅니다.
   Scheme [1] abcd
   ab(b) 과거
   a(a) 돌아와
   cd(d) 과거
   b(b) 돌아와
   ab(b) 과거
   소요 시간: a+3b+d

   구성표 [2] abcd
   ad (d) 과거
   a (a) back
   ac (c) 과거
   a (a) back
   ab (b) 과거
   시간 소요: 2a+b+c+d

   계산 예시
   Now 예 {1, 2, 5, 10}
   Plan [1] time = 17
   Plan [2] time = 19
   그래서 plan [1]이 가장 짧은 시간이 걸리므로 시간은 17

   하지만 만약 우리가 데이터 수정{ 1, 2, 2, 10}
   계획[1] 시간 = 17
   계획[2] 시간 = 16
   이번에 가장 짧은 시간이 걸리는 것이 계획[2]이며 시간은 16;

   만약 두 가지 계획을 결합하여 소요 시간을 대략적으로 계산하면
   계획 [1]: 2b
   계획 [2]: a+c
   소요 시간을 알 수 있습니다 결정적 요인이 가장 빠른 a, 두 번째로 빠른 b입니다. 두 번째로 느린 c, 2b와 a+c를 비교하여 시간이 가장 적게 걸리는 솔루션을 선택하면 됩니다.

   n > 4일 때 가장 빠른 두 사람을 이용하여 가장 느린 두 사람을 수송한다고 표현하면, 수송 후에는 인원이 2명씩 줄어듭니다.

   관련 튜토리얼: Java 비디오 튜토리얼

   다음은 참조용 AC 코드입니다

   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);
   	}
   }

   위 내용은 강을 건너는 고전적인 알고리즘 문제에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!