数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学最小化成本以减少数组：每选择两个元素，第三个元素即可免费获得
在这个问题中，我们得到一个数组，我们必须以所需的最小成本移除数组的所有元素。我们必须一次移除两个元素并将它们添加到总成本中。此外，如果我们移除两个元素并且第三个元素的值最多等于这两个元素中的最小值，则可以免费移除第三个数字。此外，给定数组的大小将大于 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：使用映射
在这个程序中，我们将使用映射并从映射的末尾获取元素，每次我们将元素分成三组，就像我们在之前的代码中所做的那样，然后对于 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))，因为我们使用映射来存储、访问和删除元素。
上述代码的空间复杂度为 O(N)，其中 N 是给定数组的大小，额外的空间因子是由于映射。
结论
在本教程中，我们实现了一个程序，以获取从数组中移除元素的最小成本，如果可能，则以 3 个一组，否则以 2 个一组，其中移除 3 个一组的元素将仅花费最大两个元素的总和。我们已经实现了两个程序，时间复杂度为 O(N*log(N))，空间复杂度为 O(1) 和 O(N)。
144 次查看
