C++ 将成本最小化以降低数组，如果选择每两个元素，第三个元素是免费的

在这个问题中，我们给出了一个数组，并且我们必须以最小的成本去除数组的所有元素。我们每次必须去除两个元素并将它们添加到总成本中。此外，如果我们去除两个元素并且第三个元素的值最多等于它们的最小值，我们可以免费删除第三个元素。也给出了给定数组的大小将大于1。

示例示例

输入

int arr[] = {7, 6, 5, 2, 9, 2};

输出

23

解释：我们可以同时移除9和7，以移除6，并且这将花费我们16个单位。然后我们可以同时移除5和2，并且可以免费移除另外2个单位，这个操作的总花费为7个单位，总体花费为23个单位。

输入：

int arr[] = {1, 2, 3, 4};

输出

10

解释：我们可以先移除4和3，然后移除2，但这将导致第一个元素1单独存在，然后我们无法移除它。所以我们不会将2与4和3一起移除，移除它会给我们带来总成本10。

方法1：使用排序

在这个方法中，我们将对数组进行排序，然后从后面遍历它。我们将以三个元素为一组传递，并只添加前两个元素的成本，直到我们达到4或两个元素，然后我们只添加两个元素的组。

例子

#include <bits/stdc++.h>
using namespace std;
// function to find the required minimum cost 
int requiredCost(int arr[], int len){
    // sort the given array by using the stl sort function 
    sort(arr, arr + len);
   int cost = 0; // variable to store the cost traversing over the array from the back side 
    for (int i = len- 1; i>= 0; i--){
       // i is 3 or 1 means 4 and 2 elements left we can only choose in groups here and cannot remove third    
       if(i == 3 || i == 1){
          cost += arr[i] + arr[i-1];
          i--;
       } else{
          // we will lose the two elements that is ith and i-1th 
          cost += arr[i] + arr[i-1];
          i -= 2; 
       }
    }   
    return cost; // returning the total cost
}
int main(){
    int arr[] = { 6, 5, 7, 9, 2, 2 }; // given array
   int len = sizeof(arr)/ sizeof(arr[0]); // getting length of array 
   cout<<"The minimum cost to remove all the elements of the array is "<< requiredCost(arr, len)<<endl;
    return 0;
}

输出

The minimum cost to remove all the elements of the array is 23

时间和空间复杂度

以上代码的时间复杂度为O(N*log(N))，其中N是给定数组中的元素数目。我们使用了内置的排序函数，导致了对数因子。

以上代码的空间复杂度为O(1)或常数，因为我们这里没有使用任何额外的空间。

方法2：使用Map

在这个程序中，我们将使用Map，并从Map的末尾获取元素，每次我们将以3个元素为一组，就像在前面的代码中所做的那样，然后对于4个和2个元素，我们将只组成2个元素的组。

例子

#include <bits/stdc++.h>
using namespace std;

int requiredCost(int arr[], int len){
   int cost = 0; // variable to store the cost 
   map<int,int>mp;
   // traversing over the array adding elements to the map
   for(int i=0; i<len; i++){
      mp[arr[i]]++;
   }
   // traversing over the map
   int rem_elements = len; // variable to track the remaining variables 
   // traversing over the map until rem_elements exits 
   while(rem_elements > 0){
      if(rem_elements == 4 || rem_elements == 2){
         auto it = mp.rbegin();
         if(it->second > 1){
            // remove 2 elements 
            cost += 2*it->first; 
            it->second -= 2;
            rem_elements -= 2; // removed 2 elements 
            if(it->second == 0){
               mp.erase(it->first);  // remove from map
            }
         } else{
            // remove current element 
            cost += it->first;
            mp.erase(it->first);
            it = mp.rbegin();
            cost += it->first;
            if(it->second == 1){
               mp.erase(it->first);
            }
            rem_elements -= 2; // removed 2 elements 
         }
      } else{
         // now we can remove three elements 
         int k = 3; 
         while(k > 0){
            auto it = mp.rbegin();
            if(k > 1){
               cost += it->first; 
            }
            it->second--;
            if(it->second == 0){
               mp.erase(it->first);
            }
            k--;
         }
         rem_elements -= 3;
      }
   }
    return cost; // returning the total cost
}
// main function 
int main(){
    int arr[] = { 6, 5, 7, 9, 2, 2 }; // given array
   int len = sizeof(arr)/ sizeof(arr[0]); // getting length of arry 
   // calling to the function 
   cout<<"The minimum cost to remove all the elements of the array is "<< requiredCost(arr, len)<<endl;
    return 0;
}

输出

The minimum cost to remove all the elements of the array is 23

时间和空间复杂度

以上代码的时间复杂度为O(N*log(N)), 因为我们使用了map来存储、访问和删除元素。

以上代码的空间复杂度为O(N), 其中N是给定数组的大小，额外的空间因子是由map引起的。

结论

在本教程中，我们实现了一个程序，用于获取从数组中移除元素的最小代价，如果可能的话，以3个元素为一组进行移除，否则以2个元素为一组，在以3个元素为一组的情况下，移除元素的代价只是最大两个元素的和。我们实现了两个程序，时间复杂度为O(N*log(N))，空间复杂度为O(1)和O(N)。