가장 부유한 더미에서 선물을 가져가세요-PHP 튜토리얼-php.cn

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

Barbara Streisand

풀어 주다： 2025-01-01 04:30:09

원래의

308명이 탐색했습니다.

Take Gifts From the Richest Pile

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개입니다.

제약조건:

힌트:

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

해결책:

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

접근하다:

최대 힙 사용:
- 최대 개수의 선물을 반복해서 쌓아야 하므로 최대 힙(우선순위 대기열)이 이상적입니다. PHP에서는 기본적으로 최대 힙으로 작동하는 우선순위 큐인 SplPriorityQueue를 사용할 수 있습니다.
- 최대 힙을 시뮬레이션하려면 SplPriorityQueue가 기본적으로 최소 힙이므로 선물 수를 음수 값으로 삽입합니다. 음수 값을 삽입하면 가장 작은 음수 값이 원래의 가장 큰 숫자를 나타냅니다.
초 단위 처리:
- 매초마다 더미에서 최대 개수의 선물을 터뜨립니다.
- 그 더미에 있는 선물 개수의 제곱근을 제외한 모든 선물을 가져가세요.
- 수정된 더미를 다시 힙으로 밀어 넣습니다.
해지:
- 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
?>

로그인 후 복사

설명:

힙 초기화:
- SplPriorityQueue는 최대 힙을 시뮬레이션하는 데 사용됩니다. insert 메소드를 사용하면 우선순위에 따라 요소를 힙에 밀어넣을 수 있습니다.
가장 큰 파일 처리:
- k번 반복의 경우 extract를 사용하여 가장 큰 파일을 추출합니다.
- 남겨진 선물의 개수는 Floor(sqrt(...))를 사용하여 현재 가장 큰 더미의 제곱근의 바닥으로 계산됩니다.
- 감소된 파일이 힙에 다시 삽입됩니다.
남은 선물 합산:
- k 연산 후에 힙의 모든 요소가 추출되고 합산되어 남은 선물의 총 개수를 구합니다.
최첨단 케이스:
- 선물이 비어 있으면 결과는 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
?>

로그인 후 복사