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

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

Description

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

입력의 첫 번째 줄에는 테스트 사례 수인 정수 T(1출력

각 테스트 사례에 대해 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!