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

この記事では、与えられた 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 などの他の言語で作成できます。この記事がお役に立てば幸いです。

以上がC++ を使用して、i*arr を最大化するように配列を再配置します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。