首頁 >後端開發 >C++ >重新排列一個陣列以最大化i*arr,使用C++

重新排列一個陣列以最大化i*arr,使用C++

WBOY
WBOY轉載
2023-08-30 15:13:04788瀏覽

重新排列一個陣列以最大化i*arr,使用C++

在本文中,我們將討論重新排列給定的 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 等)編寫此程式碼。希望本文對您有幫助。

以上是重新排列一個陣列以最大化i*arr,使用C++的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除