가장 부유한 더미에서 선물을 가져가세요

2558. 가장 많은 선물을 받아보세요

난이도: 쉬움

주제: 배열, 힙(우선순위 대기열), 시뮬레이션

다양한 더미의 선물 개수를 나타내는 정수 배열 선물을 받았습니다. 매초마다 다음을 수행합니다.

• 선물 개수가 최대인 더미를 선택하세요.
• 최대 선물 개수가 2개 이상인 경우 아무거나 선택하세요.
• 더미에 있는 선물 개수의 제곱근을 바닥에 남겨두세요. 남은 선물도 받아가세요.

k초 후 남은 선물 개수를 반환합니다.

예 1:

• 입력: 선물 = [25,64,9,4,100], k = 4
• 출력: 29
• 설명: 선물은 다음과 같은 방법으로 수령됩니다.
  • 처음 1초에 마지막 더미가 선택되고 10개의 선물이 남습니다.
  • 그런 다음 두 번째 더미가 선택되고 8개의 선물이 남습니다.
  • 그 후 첫 번째 더미가 선택되고 5개의 선물이 남습니다.
  • 마침내 마지막 더미가 다시 선택되어 3개의 선물이 남습니다.
  • 최종 남은 선물은 [5,8,9,4,3]개이므로 총 남은 선물 개수는 29개입니다.

예 2:

• 입력: 선물 = [1,1,1,1], k = 4
• 출력: 4
• 설명: 이 경우 어떤 더미를 선택하든 관계없이 각 더미에 선물 1개를 남겨야 합니다.
  • 즉, 어떤 더미도 가져갈 수 없습니다.
  • 그래서 남은 선물은 총 4개입니다.

제약조건:

• 1 3
• 1 9
• 1 3

힌트:

1. 배열에서 가장 큰 선물을 어떻게 추적할 수 있나요
2. 숫자의 제곱근을 구하는 효율적인 방법은 무엇인가요?
3. 선물이 특정 순서로 정렬되었는지 확인하면서 선물의 가치를 계속해서 더할 수 있나요?
4. 여기서 우선순위 큐나 힙을 사용할 수 있나요?

해결책:

최대 개수의 선물이 있는 더미를 반복적으로 선택해야 하므로 max-heap(우선순위 대기열)을 활용할 수 있습니다. 최대 힙을 사용하면 일정한 시간에 가장 큰 더미에 효율적으로 액세스하고 더미에서 선물을 가져온 후 힙을 업데이트할 수 있습니다.

접근하다:

1. 최대 힙 사용:

   • 최대 개수의 선물을 반복해서 쌓아야 하므로 최대 힙(우선순위 대기열)이 이상적입니다. PHP에서는 기본적으로 최대 힙으로 작동하는 우선순위 큐인 SplPriorityQueue를 사용할 수 있습니다.
   • 최대 힙을 시뮬레이션하려면 SplPriorityQueue가 기본적으로 최소 힙이므로 선물 수를 음수 값으로 삽입합니다. 음수 값을 삽입하면 가장 작은 음수 값이 원래의 가장 큰 숫자를 나타냅니다.

2. 초 단위 처리:

   • 매초마다 더미에서 최대 개수의 선물을 터뜨립니다.
   • 그 더미에 있는 선물 개수의 제곱근을 제외한 모든 선물을 가져가세요.
   • 수정된 더미를 다시 힙으로 밀어 넣습니다.

3. 해지:

   • k초 후에 또는 모든 초를 처리한 후에 중지합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2558. 가장 많은 선물을 받으세요

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

설명:

1. 힙 초기화:

   • SplPriorityQueue는 최대 힙을 시뮬레이션하는 데 사용됩니다. insert 메소드를 사용하면 우선순위에 따라 요소를 힙에 밀어넣을 수 있습니다.

2. 가장 큰 파일 처리:

   • k번 반복의 경우 extract를 사용하여 가장 큰 파일을 추출합니다.
   • 남겨진 선물의 개수는 Floor(sqrt(...))를 사용하여 현재 가장 큰 더미의 제곱근의 바닥으로 계산됩니다.
   • 감소된 파일이 힙에 다시 삽입됩니다.

3. 남은 선물 합산:

   • k 연산 후에 힙의 모든 요소가 추출되고 합산되어 남은 선물의 총 개수를 구합니다.

4. 최첨단 케이스:

   • 선물이 비어 있으면 결과는 0입니다.
   • k가 가능한 작업 수보다 크면 알고리즘이 이를 적절하게 처리합니다.

시간 복잡도:

• 힙 작업(삽입 및 추출): 각 힙 작업(삽입 및 추출)에는 O(log n)이 소요됩니다. 여기서 n은 더미 개수입니다.
• k 연산을 통한 반복: k 연산을 수행하며 각각 힙 추출과 삽입이 포함되며 둘 다 O(log n).

따라서 총 시간 복잡도는

O(k log n)입니다. 여기서 n은 파일 개수이고 k는 초 수입니다.

예제 연습:

입력:

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

1. 처음에 우선순위 큐에는 [25, 64, 9, 4, 100] 더미가 있습니다.
2. 1초 후: 100을 선택하고 10을 남겨둡니다. 남은 선물은 [25, 64, 9, 4, 10]입니다.
3. 2초 후: 64를 선택하고 8을 남겨둡니다. 남은 선물은 [25, 8, 9, 4, 10]입니다.
4. 3초 후: 25개를 선택하고 5개를 남겨둡니다. 남은 선물은 [5, 8, 9, 4, 10]입니다.
5. 4초 후: 10개를 선택하고 3개를 남겨둡니다. 남은 선물은 [5, 8, 9, 4, 3]입니다.

남은 선물의 합은 5 8 9 4 3 = 29입니다.

이 접근 방식은 최대 힙을 사용하여 문제를 효율적으로 해결하고 주어진 제약 조건 내에서 잘 수행됩니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 가장 부유한 더미에서 선물을 가져가세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!