資料結構
網路
關係資料庫管理系統 (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 次檢視
