陣列在 K 次操作後最大值的總和（透過將最大元素減半）

---

在本文中，我們將計算在 K 次操作後陣列最大值的總和，其中我們將陣列的最大值減半。

在第一種方法中，我們將實現此問題的暴力求解。在每次迭代中，我們將使用 for 迴圈查詢陣列中的最大元素。然後，我們將此元素新增到我們的答案中，然後我們將該元素減半。我們將根據要求執行 K 次迭代。然後，我們將返回答案。

在第二種方法中，我們將使用優先佇列資料結構。最初，我們將所有陣列元素插入優先佇列。然後，對於 K 次迭代，我們將從優先佇列中獲取最大元素並將其新增到答案中。然後，我們將元素減半，然後將其重新插入優先佇列。

問題陳述

給定一個包含 N 個整數的陣列和一個整數 K，我們需要在 K 次執行以下操作後找到最大值的總和。

操作 -

• 查詢陣列中的最大元素。

• 將最大元素減半。

示例

輸入

arr = {1,2,4,8,16}, K=2

輸出

24

解釋

在第一次迭代中，最大值為 16，因此我們將 16 新增到我們的答案中，並在陣列中將其減半。因此，我們的陣列變為 {1,2,4,8,8}。

在第二次迭代中，最大值為 8，因此我們將 8 新增到我們的答案中。

因此，答案 = 16+8 = 24。

輸入

arr = {8,8,8,8}, K=4

輸出

32

解釋

在第一次迭代中，最大值為 8，因此我們將 8 新增到我們的答案中，並在陣列中將其減半。因此，我們的陣列變為 {4,8,8,8}。

在第二次迭代中，最大值仍然是 8，因此我們將 8 新增到我們的答案中，並在陣列中將其減半。因此，我們的陣列變為 {4,4,8,8}。

類似地，我們執行第三次和第四次迭代。

因此，答案 = 8+8+8+8 = 32。

輸入

arr = {2,33,71,81,93}, K=10

輸出

459

解釋

在第一次迭代中，最大值為 93，因此我們將 93 新增到我們的答案中，並在陣列中將其減半。因此，我們的陣列變為 {2,33,71,81,46}。

類似地，我們執行剩餘的 9 次操作以獲得最終答案。

因此，答案 = 93+81+71+46+40+35+33+23+20+17 = 459。

方法 1

在這種方法中，我們將使用蠻力方法來解決給定問題。我們將使用一個 while 迴圈，它將執行 K 次。在 while 迴圈的每次迭代中，我們將使用一個 for 迴圈，它將遍歷陣列並找到陣列中存在的元素的最大值和最大值元素的索引。然後，我們將此最大值新增到我們的答案中，並將陣列中的值減半。while 迴圈結束後，我們將返回答案。

演算法

• 步驟 1 - 建立一個將執行 K 次的 while 迴圈。

• 步驟 2 - 在 while 迴圈的每次迭代中

• 步驟 2.1 - 建立一個遍歷陣列元素的 for 迴圈

• 步驟 2.2 - 查詢陣列的最大元素並將其儲存在一個變數 mx 中。

• 步驟 2.3 - 還找到陣列中最大元素的索引，並將其儲存在另一個變數 ind 中。

• 步驟 3.1 - 將變數 mx 新增到答案中。

• 步驟 3.2 - 使用索引 ind 訪問元素，將 mx 的值減半。

• 步驟 4.1 - while 迴圈結束後，返回答案。

示例

#include <bits/stdc++.h>
using namespace std;
int sums_of_maximum(vector<int> &arr,int K){
   int N = arr.size();
   int res = 0;
   while(K--){
      int mx = arr[0];
      int ind = 0;
      for(int i=1;i<N;i++){
         if(arr[i]>mx){
            mx = arr[i];
            ind = i;
         }
      }
      res = res + mx;
      arr[ind] = arr[ind]/2;
   }
   return res;
}
int main(){
   vector<int> arr = {2, 33, 71, 81, 93};
   int K = 10;
   cout<<sums_of_maximum(arr,K)<<endl;
   return 0;
}

輸出

459

時間複雜度 - O(N^2)，其中 N 是陣列中的元素數量。

空間複雜度 - O(N)

方法 2

在這種方法中，我們將使用優先佇列資料結構（最大堆）來儲存陣列的元素，並在 log(N) 時間內獲取陣列的最大值，從而降低時間複雜度。我們將陣列的所有元素儲存在優先佇列中，並且對於 K 次迭代中的每一次，我們將取出陣列的最大元素，將其新增到我們的答案中，將其減半，最後將該元素重新推入佇列。

演算法

• 步驟 1 - 建立一個優先佇列。

• 步驟 1.1 - 將陣列的所有元素插入優先佇列。

• 步驟 2 - 建立一個將執行 K 次的 while 迴圈。

• 步驟 3 - 在 while 迴圈的每次迭代中

• 步驟 3.1 - 從優先佇列中獲取陣列的最大元素。

• 步驟 3.2 - 將最大元素新增到答案中。

• 步驟 3.3 - 將最大元素減半，並將其重新推入佇列。

• 步驟 4.1 - while 迴圈結束後，返回答案。

示例

#include <bits/stdc++.h>
using namespace std;
int sums_of_maximum(vector<int> &arr,int K){
   int N = arr.size();
   priority_queue<int> ele;
   for(int i=0;i<N;i++)ele.push(arr[i]);
   int res = 0;
   while(K--){
      int mx = ele.top();
      ele.pop();
      res = res + mx;
      mx = mx/2;
      ele.push(mx);
   }
   return res;
}
int main(){
   vector<int> arr = {2, 33, 71, 81, 93};
   int K = 10;
   cout<<sums_of_maximum(arr,K)<<endl;
   return 0;
}

輸出

459

時間複雜度 – O(N + K*log(N))，其中 N 是陣列中的元素數量。

空間複雜度 – O(N)，用於儲存佇列中的元素。