Bahagikan Pemain Kepada Pasukan yang Sama Kemahiran

2491. Bahagikan Pemain Kepada Pasukan Yang Sama Kemahiran

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Dua Penunjuk, Isih

Anda diberi kemahiran tatasusunan integer positif genap panjang n di mana kemahiran[i] menandakan kemahiran pemain i^ke. Bahagikan pemain kepada n / 2 pasukan bersaiz 2 supaya jumlah kemahiran setiap pasukan adalah sama.

kimia sesebuah pasukan adalah sama dengan produk kemahiran pemain dalam pasukan itu.

Kembalikan jumlah kimia semua pasukan, atau kembalikan -1 jika tiada cara untuk membahagikan pemain kepada pasukan supaya jumlah kemahiran setiap pasukan adalah sama.

Contoh 1:

• Input: kemahiran = [3,2,5,1,3,4]
• Output: 22
• Penjelasan:
  • Bahagikan pemain kepada pasukan berikut: (1, 5), (2, 4), (3, 3), di mana setiap pasukan mempunyai jumlah kemahiran sebanyak 6.
  • Jumlah kimia semua pasukan ialah: 1 * 5 2 * 4 3 * 3 = 5 8 9 = 22.

Contoh 2:

• Input: kemahiran = [3,4]
• Output: 112
• Penjelasan:
  • Kedua-dua pemain membentuk satu pasukan dengan jumlah kemahiran 7.
  • Kimia pasukan ialah 3 * 4 = 12.

Contoh 3:

• Input: kemahiran = [1,1,2,3]
• Output: -1
• Penjelasan: Tiada cara untuk membahagikan pemain kepada pasukan supaya jumlah kemahiran setiap pasukan adalah sama.

Kekangan:

• 2 <= kemahiran.panjang <= 10⁵
• kemahiran.panjangnya genap.
• 1 <= kemahiran[i] <= 1000

Petunjuk:

1. Cuba susun tatasusunan kemahiran.
2. Adalah optimum untuk memasangkan pemain yang paling lemah dengan pemain yang paling kuat.

Penyelesaian:

Kita boleh mengikut petunjuk yang diberikan dan menggunakan pendekatan tamak. Berikut ialah pecahan terperinci penyelesaian:

Langkah-langkah:

1. Isih Tatasusunan Kemahiran: Isih membolehkan kami menggandingkan pemain paling lemah (nilai terkecil) dengan pemain terkuat (nilai terbesar) dengan cekap dengan cekap.

2. Semak Gandingan Sah: Jumlah kemahiran setiap pasukan hendaklah sama. Selepas menyusun, kami akan memasangkan elemen terkecil dan terbesar, kemudian yang kedua terkecil dengan yang kedua terbesar, dan seterusnya. Jika pada bila-bila masa, jumlah pasangan berbeza daripada jumlah sebelumnya, adalah mustahil untuk membahagikan pemain kepada pasukan yang sah, dan kami harus mengembalikan -1.

3. Kira Kimia: Kimia setiap pasukan adalah hasil daripada dua kemahiran dalam pasukan itu. Jumlahkan semua nilai kimia untuk setiap pasukan yang sah.

4. Kembalikan Jumlah Kimia: Jika semua pasukan mempunyai jumlah kemahiran yang sama, kembalikan jumlah kimia mereka.

Mari laksanakan penyelesaian ini dalam PHP: 2491. Bahagikan Pemain Kepada Pasukan yang Sama Kemahiran

/**


@param Integer[] $skill
@return Integer
/
function dividePlayers($skill) {
...
...
...
/*


go to ./solution.php
*/
}





// Test cases

$skill1 = [3, 2, 5, 1, 3, 4];

$skill2 = [3, 4];

$skill3 = [1, 1, 2, 3];

echo dividePlayers($skill1) . "\n";  // Output: 22

echo dividePlayers($skill2) . "\n";  // Output: 12

echo dividePlayers($skill3) . "\n";  // Output: -1

?>





  

  

  Penjelasan:




Isih: Kemahiran tatasusunan diisih untuk memastikan kita boleh memasangkan nilai terkecil dan terbesar dengan cekap.
Dua Penunjuk: Kami menggunakan dua penunjuk ($i bermula dari awal dan $j bermula dari akhir). Untuk setiap pasangan yang sah (terkecil dan terbesar), kami menyemak sama ada jumlah mereka adalah sama dengan teamSkillSum yang dijangkakan. Jika tidak, adalah mustahil untuk membahagikan pemain kepada beberapa pasukan.
Pengiraan Kimia: Jika pasangan itu sah, kimia dikira sebagai hasil darab kedua-dua nilai ($kemahiran[$i] * $kemahiran[$j]), dan kami teruskan menambahnya kepada jumlah kimia.

Kes Tepi:


Jika pasukan tidak dapat dibentuk kerana jumlah yang tidak sama, kami kembalikan -1.
Kod ini mengendalikan kes dengan panjang sekata dan memastikan semua pemain dipasangkan dengan betul.





  
  
  Kerumitan Masa:



Mengisih tatasusunan mengambil masa O(n log n), dan lintasan dua mata mengambil masa O(n). Oleh itu, kerumitan masa keseluruhan ialah O(n log n), yang cekap memandangkan kekangan.


Penyelesaian ini berfungsi dalam kekangan yang diberikan sehingga 105 pemain.

Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Bahagikan Pemain Kepada Pasukan yang Sama Kemahiran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!