플레이어를 동일한 기술을 가진 팀으로 나누기

2491. 플레이어를 동일한 실력의 팀으로 나누기

난이도:중

주제: 배열, 해시 테이블, 두 포인터, 정렬

당신은 짝수 길이 n의 양의 정수 배열 스킬을 받았습니다. 여기서 Skill[i]는 i^번째 플레이어의 스킬을 나타냅니다. 각 팀의 총 실력이 동일되도록 플레이어를 n/2개의 크기 2 팀으로 나눕니다.

팀의 케미스트리는 그 팀 선수들의 실력 산물과 같습니다.

모든 팀의 케미스트리의 합을 반환하거나, 각 팀의 총 실력이 동일하도록 플레이어를 팀으로 나눌 수 있는 방법이 없는 경우 -1을 반환합니다..

예 1:

• 입력: 스킬 = [3,2,5,1,3,4]
• 출력: 22
• 설명:
  • 플레이어를 다음 팀으로 나눕니다: (1, 5), (2, 4), (3, 3), 각 팀의 총 스킬은 6입니다.
  • 모든 팀의 케미스트리의 합은 1*5 2*4 3*3 = 5 8 9 = 22입니다.

예 2:

• 입력: 스킬 = [3,4]
• 출력: 112
• 설명:
  • 두 선수가 총 스킬 7로 팀을 구성합니다.
  • 팀 케미스트리는 3*4=12입니다.

예 3:

• 입력: 스킬 = [1,1,2,3]
• 출력: -1
• 설명: 각 팀의 총 실력이 동일하도록 선수들을 팀으로 나눌 수 있는 방법은 없습니다.

제약조건:

• 2 5
• Skill.length가 짝수입니다.
• 1

힌트:

1. 스킬 배열을 정렬해 보세요.
2. 가장 약한 플레이어와 가장 강한 플레이어를 짝짓는 것이 항상 최적입니다.

해결책:

제공된 힌트를 따르고 탐욕스러운 접근 방식을 사용할 수 있습니다. 솔루션에 대한 자세한 내용은 다음과 같습니다.

단계:

1. 스킬 배열 정렬: 정렬을 사용하면 가장 약한 플레이어(가장 작은 값)와 가장 강한 플레이어(가장 큰 값)를 효율적으로 짝을 이룰 수 있습니다.

2. 유효한 페어링 확인: 각 팀의 기술 합계가 동일해야 합니다. 정렬 후에는 가장 작은 요소와 가장 큰 요소를 쌍으로 묶은 다음 두 번째로 작은 요소와 두 번째로 큰 요소 등을 연결합니다. 어떤 시점에서든 쌍의 합이 이전 합과 다른 경우 플레이어를 유효한 팀으로 나눌 수 없으며 -1을 반환해야 합니다.

3. 조직력 계산: 각 팀의 조직력은 해당 팀의 두 기술의 산물입니다. 유효한 각 팀의 모든 화학 값을 합산합니다.

4. 전체 케미스트리 반환: 모든 팀의 전체 스킬이 동일한 경우 케미스트리의 합을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2491. 플레이어를 동일한 실력의 팀으로 나누기

<p><?php<br>
/**</p>

<ul>
<li>@param Integer[] $skill</li>
<li>@return Integer
<em>/
function dividePlayers($skill) {
...
...
...
/</em>*

<ul>
<li>go to ./solution.php
*/
}
</li>
</ul>
</li>
</ul>

<p>// Test cases<br>
$skill1 = [3, 2, 5, 1, 3, 4];<br>
$skill2 = [3, 4];<br>
$skill3 = [1, 1, 2, 3];</p>

<p>echo dividePlayers($skill1) . "\n";  // Output: 22<br>
echo dividePlayers($skill2) . "\n";  // Output: 12<br>
echo dividePlayers($skill3) . "\n";  // Output: -1<br>
?></p>

설명:

1. 정렬: 배열 기술은 가장 작은 값과 가장 큰 값을 효율적으로 쌍으로 연결할 수 있도록 정렬됩니다.

2. 두 개의 포인터: 두 개의 포인터(처음부터 시작하는 $i와 끝부터 시작하는 $j)를 사용합니다. 각 유효한 쌍(최소 및 최대)에 대해 해당 합계가 예상되는 teamSkillSum과 동일한지 확인합니다. 그렇지 않으면 선수들을 팀으로 나누는 것이 불가능합니다.

3. 화학 계산: 쌍이 유효한 경우 화학은 두 값($skill[$i] * $skill[$j])의 곱으로 계산되며, 계속해서 전체 케미스트리에 추가해 보세요.

4. 최첨단 케이스:

   • 합계가 다르기 때문에 팀을 구성할 수 없는 경우 -1을 반환합니다.
   • 코드는 길이가 짝수인 경우를 처리하고 모든 플레이어가 올바르게 페어링되었는지 확인합니다.

시간 복잡도:

• 배열 정렬에는 O(n log n)이 소요되고, 두 포인터 순회에는 O(n)이 소요됩니다. 따라서 전체 시간 복잡도는 O(n log n)이며 이는 제약 조건을 고려하면 효율적입니다.

이 솔루션은 최대 10⁵명의 플레이어

라는 주어진 제약 내에서 작동합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 플레이어를 동일한 기술을 가진 팀으로 나누기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!