数组在 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)，用于存储队列中的元素。