가방에 담긴 공의 최소 한도

1760. 가방 속 공의 최소 한도

난이도:중

주제: 배열, 이진 검색

i^번째 백에 num[i]개의 공이 포함된 정수 배열 nums가 제공됩니다. 정수 maxOperations도 제공됩니다.

최대 maxOperations 횟수로 다음 작업을 수행할 수 있습니다.

• 공 한 봉지를 가져다가 공 개수가 양수인 두 개의 새 봉지로 나눕니다.
  • 예를 들어 5개의 공이 들어 있는 가방은 1개와 4개의 공이 들어 있는 두 개의 새로운 가방 또는 2개와 3개의 공이 들어 있는 두 개의 새로운 가방이 될 수 있습니다.

페널티는 가방에 들어 있는 최대개의 공 수입니다. 수술 후 불이익을 최소화하고 싶으신 분.

반환작업 수행 후 가능한 최소 페널티.

예 1:

• 입력: nums = [9], maxOperations = 2
• 출력: 3
• 설명:
  • 공 9개가 들어있는 가방을 6호와 3호 가방 2개로 나누어 보세요. [9] -> [6,3].
  • 공 6개가 들어있는 가방을 3호와 3호 가방 2개로 나누어주세요. [6,3] -> [3,3,3].
  • 공이 가장 많은 가방에는 공이 3개 있으므로 페널티는 3이고 3을 돌려주어야 합니다.

예 2:

• 입력: nums = [2,4,8,2], maxOperations = 4
• 출력: 2
• 설명:
  • 볼 8개가 들어있는 가방을 4사이즈와 4사이즈 가방 2개로 나누어주세요. [2,4,8,2] -> [2,4,4,4,2].
  • 공 4개가 들어있는 가방을 크기 2와 2의 가방 2개로 나누어주세요. [2,4,4,4,2] -> [2,2,2,4,4,2].
  • 볼 4개가 들어있는 가방을 사이즈 2와 2의 가방 2개로 나누어주세요. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
  • 볼 4개가 들어있는 가방을 크기 2와 2의 가방 2개로 나누어주세요. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
  • 공이 가장 많은 가방에 공이 2개 있으므로 벌칙은 2이고 2를 돌려주어야 합니다.

제약조건:

• 1 5
• 1 9

힌트:

1. 가방의 최대 크기를 알고 있다면 질문을 바꿔보겠습니다. 만들 수 있는 최소 가방 개수는 얼마입니까
2. 최대 크기가 증가하면 최소 가방 수가 감소하므로 최대 크기를 이진 검색할 수 있습니다

해결책:

이진 검색을 사용하여 가능한 최소 페널티를 찾을 수 있습니다. 핵심 통찰력은 주어진 페널티를 달성할 수 있는지 여부를 판단할 수 있으면 이진 검색을 사용하여 검색 범위를 좁힐 수 있다는 것입니다.

해결 단계:

1. 이진 검색 설정:

   • 최소 페널티는 1입니다(모든 공은 단일 공 가방으로 분할됩니다).
   • 최대 페널티는 숫자 배열에서 가장 큰 숫자입니다.

2. 타당성 검사:

   • 주어진 페널티 중간에 대해 최대 maxOperations 분할로 이를 달성할 수 있는지 확인하세요.
   • 이렇게 하려면 각 가방 크기(숫자)에 대해 모든 가방의 중간 공 이하를 만드는 데 필요한 분할 수를 계산하세요. 총 분할 수가 maxOperations를 초과하는 경우 페널티 mid는 불가능합니다.

3. 반복:

   • 이진 검색을 사용하여 페널티 미드가 가능한지 여부에 따라 [낮음, 높음] 범위를 조정하세요.

이 솔루션을 PHP: 1760으로 구현해 보겠습니다. 가방 속 공의 최소 제한

<?php /**
 * @param Integer[] $nums
 * @param Integer $maxOperations
 * @return Integer
 */
function minimumSize($nums, $maxOperations) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a penalty is feasible
 *
 * @param $nums
 * @param $maxOperations
 * @param $penalty
 * @return bool
 */
function canAchievePenalty($nums, $maxOperations, $penalty) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$nums = [9];
$maxOperations = 2;
echo minimumSize($nums, $maxOperations); // Output: 3

// Example 2
$nums = [2, 4, 8, 2];
$maxOperations = 4;
echo minimumSize($nums, $maxOperations); // Output: 2
?>

설명:

1. 이진 검색:

   • 검색 공간은 1과 nums 배열의 최대 숫자 사이입니다.
   • 중간점은 현재 테스트 중인 페널티를 나타냅니다.

2. 타당성 확인(canAchievePenalty):

   • 각 가방에 대해 필요한 분할을 계산하여 모든 가방에 중간 볼이 이하인지 확인하세요.
     • ceil(balls / mid) - 1은 필요한 분할 수를 나타냅니다.
   • 총 분할 수가 maxOperations를 초과하는 경우 페널티가 적용되지 않습니다.

3. 검색 공간 조정:

   • 페널티가 가능하다면 상한(높음=중간)을 줄이세요.
   • 그렇지 않은 경우 하한을 늘립니다(낮음 = 중간 1).

4. 결과:

   • 루프가 종료되면 low에는 가능한 가장 작은 페널티가 포함됩니다.

복잡성:

• 시간 복잡도: O(n .log(max(nums)))
  • 이진 검색은 O(log(max(nums)))에서 실행되며 각 중간점에 대한 타당성 검사에는 O(n).
• 공간 복잡도: O(1), 일정한 추가 공간만 사용하기 때문입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서

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

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

• 링크드인
• 깃허브

위 내용은 가방에 담긴 공의 최소 한도의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!