如果每选择两个元素，第三个元素是免费选择的，则最小化数组的成本
这个问题给我们一个数组，我们需要以最低的成本移除数组中的所有元素。我们需要一次移除两个元素，并将它们添加到总成本中。此外，如果我们移除两个元素，并且第三个元素的值最多等于其中的最小值，那么我们可以免费移除第三个数字。此外，给定数组的大小必然大于 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 一起移除，移除 1 会导致总成本为 10。
方法 1:使用排序
在此方法中，我们将对数组进行排序，然后从后端遍历。我们将传入三个元素组成的数组，并仅添加前两个元素的成本，直到达到 4 或两个元素，然后我们仅添加两个元素组成的数组。
示例
#include <bits/stdc++.h>
using namespace std;
// 用于查找所需最小成本的函数
int requiredCost(int arr[], int len){
// 使用 stl sort 函数对给定数组进行排序
sort(arr, arr + len);
int cost = 0; // 用于存储从数组后端遍历成本的变量
for (int i = len- 1; i>= 0; i--){
// i 为 3 或 1 表示剩余 4 和 2 个元素，我们只能按组选择，不能删除第三个
if(i == 3 || i == 1){
cost += arr[i] + arr[i-1];
i--;
} else{
// 我们将丢失第 i 个和第 i-1 个元素
cost += arr[i] + arr[i-1];
i -= 2;
}
}
return cost; // 返回总成本
}
int main(){
int arr[] = { 6, 5, 7, 9, 2, 2 }; // 给定数组
int len = sizeof(arr)/ sizeof(arr[0]); // 获取数组长度
cout<<"删除数组中所有元素的最小成本为 "<< requiredCost(arr, len)<<endl;
return 0;
}
输出
删除数组中所有元素的最小成本为 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; // 存储成本的变量
map<int,int>mp;
// 遍历数组并向 map 添加元素
for(int i=0; i<len; i++){
mp[arr[i]]++;
}
// 遍历 map
int rem_elements = len; // 用于跟踪剩余变量的变量
// 遍历 map 直到 rem_elements 退出
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; // 删除了 2 个元素
if(it->second == 0){
mp.erase(it->first); // remove from map
}
} else{
// 移除当前元素
cost += it->first;
mp.erase(it->first);
it = mp.rbegin();
cost += it->first;
if(it->second == 1){
mp.erase(it->first);
}
rem_elements -= 2; // 删除了 2 个元素
}
} else{
// 现在我们可以删除三个元素
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; // 返回总成本
}
// 主函数
int main(){
int arr[] = { 6, 5, 7, 9, 2, 2 }; // 给定数组
int len = sizeof(arr)/ sizeof(arr[0]); // 获取数组长度
// 调用函数
cout<<"删除数组所有元素的最小成本为 "<< requiredCost(arr, len)<<endl;
return 0;
}
输出
删除数组中所有元素的最小成本为 23
时间和空间复杂度
上述代码的时间复杂度为 O(N*log(N))，因为我们使用了 map 来存储、移除和删除元素。
上述代码的空间复杂度为 O(N)，其中 N 是给定数组的大小，额外的空间因素是由于 map 造成的。
结论
在本教程中，我们实现了一个程序，用于计算从数组中删除元素的最小成本，如果可能的话，以 3 个元素为一组;否则，以 2 个元素为一组。其中，删除 3 个元素的组中元素的成本仅为最大两个元素之和。我们实现了两个程序，时间复杂度为 O(N*log(N))，空间复杂度为 O(1) 和 O(N)。
