C++を使用してi*arr[i]を最大化するように配列を再配置します

この記事では、n個の数値の特定の配列を再配置する問題について説明します。基本的に、配列から要素を選択する必要があります。各要素を選択するために、現在の要素の値*現在の要素の前に選択された要素の数によって評価されるいくつかのポイントを取得します。最大のポイントを取得するには、要素を選択する必要があります。例-

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

解決策を見つけるためのアプローチ

例を見ると、最大のポイントを取得するためにそれが得られ、最小から最大の要素を選択する必要があります。解決策を見つけるためのアプローチは、

• 指定された配列を昇順で並べ替えます。
• インデックス0から終了まで要素の選択を開始します。
• 各要素を選択して得たポイントを計算します。

例

#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;
}

出力

Maximum points: 63

上記のコードの説明

このC++コードは理解しやすいです。最初に配列を並べ替えてから、forループを使用して配列をトラバースし、各要素を最初から最後まで選択して得られるポイントを計算します。

結論

この記事では、ポイントがi * arr [i]によって計算される最大ポイントを取得するために、配列内の要素を選択する問題について説明します。この問題を解決し、最大のポイントを獲得するために、貪欲なアプローチを適用します。同じことを行うためのC++コードについても説明します。このコードは、C、Java、Pythonなどの他の言語で記述できます。この記事がお役に立てば幸いです。