최대 평균 합격률

1792. 최대 평균 합격률

난이도:중

주제: 배열, 탐욕, 힙(우선순위 대기열)

학생들로 구성된 반이 있는 학교가 있는데, 각 반마다 기말고사를 치르게 됩니다. 2D 정수 배열 클래스가 제공됩니다. 여기서 클래스[i] = [pass_i, total_i]입니다. iⁱ반에는 총_i명의 학생이 있는데, 합격_i명만이 시험에 합격한다는 것을 미리 알고 계시죠.

정수 extraStudents도 제공됩니다. 배정된 모든 수업의 시험에 합격할 것을 보장하는 또 다른 extraStudents 뛰어난 학생들이 있습니다. 모든 수업에서 평균 합격 비율을 최대화

하는 방식으로 각 extraStudents 학생을 수업에 할당하려고 합니다.

한 학급의 합격률은 시험에 합격할 해당 학급의 학생 수를 해당 학급의 전체 학생 수로 나눈 값입니다. 평균 합격률

은 전체 과목의 합격률을 합하여 과목 수로 나눈 값입니다.

extraStudents 학생을 할당한 후 최대 ^{가능한 평균 합격률을 반환합니다. 실제 답변의 10}~5

이내 답변을 인정합니다.

예 1:

• 입력:
클래스 = [[1,2],[3,5],[2,2]], extraStudents = 2
• 출력:
0.78333
• 설명:
첫 번째 수업에 두 명의 추가 학생을 할당할 수 있습니다. 평균 합격률은 (3/4 3/5 2/2) / 3 = 0.78333입니다.

예 2:

• 입력:
클래스 = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
• 출력:
4
• 설명:
0.53485

제약조건:

• ^{1 5}
classes[i].length == 2
• _{1 i i ⁵}
• ^{1 5}

힌트:

1. 수업에 학생을 추가하면 합격률이 얼마나 변하는지 주목하세요. 계속해서 학생을 추가하면 합격률의 변화는 어떻게 되나요? 수업에 더 많은 학생을 추가할수록 합격률의 변화는 작아집니다.
2. 합격률의 변화는 학생이 늘어날수록 항상 감소하므로 각 수업에 가장 먼저 추가하는 학생이 합격률에 가장 큰 변화를 가져옵니다.
3. 각 수업의 합격률은 균등하게 적용되므로 다른 수업 중에서 가장 큰 변화를 일으키는 수업에 학생을 배치하는 것이 항상 최적입니다.
4. 현재 수업 규모의 최대 힙을 유지하고 합격 비율 변경에 따라 주문하세요. 각 추가 학생에 대해 힙의 맨 위를 차지하고 클래스 크기를 업데이트한 후 다시 힙에 넣습니다.

해결책:

최대 힙(우선순위 큐)을 사용할 수 있습니다. 학생을 추가할 때 가장 많은 혜택을 받는(합격률 변화가 최대화되는) 반을 효율적으로 찾아야 하기 때문입니다.

접근하다:

1. 이득 계산 이해:

   • 수업에 학생 한 명을 추가할 때 합격 비율의 변화는 다음과 같이 계산할 수 있습니다. 이득 = (통과 1)/(총 1) - 통과/총
   • 추가 학생을 최적으로 분배하여 모든 수업의 합격률 합계를 최대화하는 것이 과제입니다.

2. 최대 힙 사용:

   • 각 클래스에 대해 초기 게인을 계산하고 클래스 세부정보와 함께 최대 힙에 삽입합니다.
   • 각 힙 요소는 튜플([음수 이득, 통과, 합계])입니다. (PHP의 SplPriorityQueue는 기본적으로 최소 힙이기 때문에 음의 이득을 사용합니다.)

3. 추가 학생을 반복적으로 배포:

   • 힙에서 최대 이득을 얻은 클래스를 팝합니다.
   • 해당 클래스에 학생 한 명을 추가하고 게인을 다시 계산한 후 다시 힙에 푸시합니다.
   • 모든 extraStudents가 배포될 때까지 반복합니다.

4. 최종 평균 계산:

   • 추가 학생을 모두 배정한 후 전체 수업의 평균 합격률을 계산합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1792. 최대 평균 합격률

<?php /**
 * @param Integer[][] $classes
 * @param Integer $extraStudents
 * @return Float
 */
function maxAverageRatio($classes, $extraStudents) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Calculate the extra pass ratio when a student is added to the class
 *
 * @param $pass
 * @param $total
 * @return float|int
 */
private function extraPassRatio($pass, $total)
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$classes = [[1, 2], [3, 5], [2, 2]];
$extraStudents = 2;
echo maxAverageRatio($classes, $extraStudents); // Output: 0.78333

$classes = [[2, 4], [3, 9], [4, 5], [2, 10]];
$extraStudents = 4;
echo maxAverageRatio($classes, $extraStudents); // Output: 0.53485
?>

설명:

1. 힙 설정:

   • 우리는 추가 학생이 추가될 때 합격률이 향상될 가능성을 기준으로 수업의 우선순위를 지정하기 위해 max-heap(우선순위 대기열)을 사용합니다.
   • PHP에서는 SplPriorityQueue가 힙으로 사용됩니다. 우선순위 값이 높을수록 수업이 더 빨리 처리됩니다.

2. 추가 학생 배분:

   • 각 추가 학생에 대해 힙에서 개선 가능성이 가장 높은 클래스를 추출합니다.
   • 해당 수업에 학생 한 명을 추가한 후 잠재적인 개선 사항을 다시 계산하여 힙에 다시 삽입합니다.

3. 최종 평균 계산:

   • 추가 학생을 모두 배분한 후 모든 수업의 총 합격률을 계산하여 평균을 반환합니다.

4. 정밀성:

   • 계산은 부동 소수점 연산을 사용하여 수행되므로 필요에 따라 답이 10^-5까지 정확하도록 보장됩니다.

복잡성:

• 시간 복잡성:

  • 힙 삽입 및 추출에는 O(log N)이 필요합니다. 여기서 N은 클래스 수입니다.
  • extraStudents 반복의 경우 복잡성은 O(extraStudents x log N)
  입니다.
  • 최종 합격률 합산은 O(N)입니다.

• 공간 복잡성:

  • 힙은 N 요소를 저장하므로 공간 복잡도는 O(N)
  입니다.

이 구현은 추가 학생을 효율적으로 분배하고 최대 평균 합격률을 계산합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 최대 평균 합격률의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!