Susun semula tatasusunan untuk memaksimumkan i*arr, menggunakan C++

Dalam artikel ini, kita akan membincangkan masalah menyusun semula susunan n nombor yang diberikan. Pada asasnya, kita perlu memilih elemen daripada tatasusunan. Untuk memilih setiap elemen, kami mendapat beberapa mata yang akan dinilai oleh nilai elemen semasa * bilangan elemen yang dipilih sebelum elemen semasa. Anda harus memilih elemen untuk mendapatkan markah tertinggi. Contohnya -

Input : arr[ ] = { 3, 1, 5, 6, 3 }

If we select the elements in the way it is given, our points will be
   = 3 * 0 + 1 * 1 + 5 * 2 + 6 * 3 + 3 * 4
   = 41
To maximize the points we have to select the elements in order { 1, 3, 3, 5, 6 }
   = 1 * 0 + 3 * 1 + 3 * 2 + 5 * 3 + 6 * 4
   = 48(maximum)

Output : 48

Input : arr[ ] = { 2, 4, 7, 1, 8 }
Output : 63

Kaedah untuk mencari penyelesaian

Melihat contoh ini, kita perlu mendapatkan titik maksimum, kita perlu memilih elemen dari kecil ke besar. Penyelesaian ditemui dengan,

• menyusun tatasusunan yang diberikan dalam tertib menaik.
• Mula memilih elemen dari indeks 0 hingga akhir.
• Kira markah yang diperolehi dengan memilih setiap elemen.

Contoh

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int main () {
   int arr[] = { 2, 4, 7, 1, 8 };
   int n = sizeof (arr) / sizeof (arr[0]);
   // sorting the array
   sort (arr, arr + n);

   int points = 0;
   // traverse the array and calculate the points
   for (int i = 0; i < n; i++) {
      points += arr[i] * i;
   }
   cout << "Maximum points: " << points;
   return 0;
}

Output

Maximum points: 63

Penerangan kod di atas

Kod C++ ini mudah difahami. Mula-mula kita mengisih tatasusunan dan kemudian menggunakan gelung for untuk mengulang tatasusunan dan mengira skor yang diperoleh dengan memilih setiap elemen dari awal hingga akhir.

Kesimpulan

Dalam artikel ini, kami membincangkan masalah memilih elemen dalam tatasusunan untuk mendapatkan titik maksimum, di mana titik dikira oleh i * arr[i]. Kami mengamalkan pendekatan tamak untuk menyelesaikan masalah ini dan memperoleh markah maksimum. Juga membincangkan kod C++ untuk melakukan perkara yang sama, kita boleh menulis kod ini dalam mana-mana bahasa lain seperti C, java, Python dll. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Susun semula tatasusunan untuk memaksimumkan i*arr, menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!