資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過將給定陣列拆分為大小為 K 的子集並將每個子集中的最高 K/2 個元素新增到成本中來最小化成本。
拆分陣列意味著我們必須將陣列劃分並建立子集。在此問題中，我們給定一個大小為 n 的整數陣列和一個整數 k，我們的目標是透過將整個給定陣列拆分為大小為 k 的子集並將每個子集中的最高 k/2 個元素新增到成本中來計算最低成本。
注意：這裡我們考慮 k/2 的上取整。
讓我們看看下面的示例及其解釋，以便更好地理解問題。
示例
輸入
n: 4 array: [ 3, 4, 2, 1 ] k: 2
輸出
6
解釋：這裡我們將給定陣列拆分為 [ 3, 4 ] 和 [ 2, 1 ]
現在我們必須將每個子集中的最高 k/2 個元素新增到成本中。
k/2 = 2/2 = 1。
成本 = 4 + 2 = 6
輸入
n: 10 array: [ 3, 5, 2, 6, 7, 4, 1, 8, 11, 10 ] k: 5
輸出
41
解釋：這裡我們將給定陣列拆分為 [ 3, 5, 2, 4, 1 ] 和 [ 6, 7, 8, 11, 10 ]
現在我們必須將每個子集中的最高 k/2 個元素新增到成本中。
k/2 = 5/2 = 2.5，現在 [2.5] 的上取整 = 3。
我們必須將每個子集中的 3 個最高元素新增到成本中
成本 = 3 + 4 + 5 + 8 + 11 + 10 = 41
貪心演算法
這種方法的思路很簡單，我們貪心地思考，因為我們知道我們必須透過將陣列拆分為 k 個子集並將 k/2 個最高元素的上取整新增到成本中來最小化成本，因此根據觀察，如果對陣列進行排序，那麼我們從後面遍歷陣列。之後，對於每個大小為 k 的子集，我們將 k/2 個最高元素新增到成本中，我們得到了最小化成本。
讓我們逐步討論以下方法-
我們建立了一個名為 calculateLowestCost 的函式，它接受陣列大小、陣列和 k 等引數。
在函式中，建立一個名為 "minimizeCost" 的變數來儲存最終答案。
使用 sort 函式對陣列進行排序
將 k/2 的上取整儲存在 "updateK" 變數中
從 n-1 到大於等於 0 遍歷迴圈。
將 'updateK' 儲存到變數 j 中以維護我們需要新增到成本 ("minimizeCost") 中的元素的數量
將 k 儲存到變數 tempK 中以維護大小為 k 的子集
使用 while 迴圈將 j 個元素新增到 minimizeCost 中，並減少 j、tempK 和 i。
透過從 i 中減去剩餘的 tempK 來更新大小為 k 的子集的 i。
返回 minimzeCost
讓我們看看下面的程式碼，以便更好地理解上述方法。
示例
#include <bits/stdc++.h>
using namespace std;
// Create a function "calculateLowestCost"
int calculateLowestCost( int n, int array [], int k ) {
// Create variable "minimizeCost" to store the final cost
int minimizeCost = 0;
// Using STL function sort, sorting an array
sort(array , array + n);
// Create variable updateK to store the ceil of k/2
int updateK = ceil (k/2.0);
// Traverse the array using for loop from the end as we need to add k/2
//highest element of each subset of size k
for ( int i = n-1; i >= 0; i-- ) {
// store ceil of k/2 to varible j
int j = updateK;
// store k to tempK to maintain the subset of size k
int tempK = k;
// Traverse the while loop to add ceil of k/2 highest element of the subset of size k
while ( i>=0 && j--){
minimizeCost += array[i];
tempK --;
i--;
}
// Update i for the subset of size k
if(tempK){
i -= tempK;
}
i++;
}
// Return Final cost
return minimizeCost;
}
int main(){
int n = 4; // Givn the siz of the array
int array [] = { 3, 4, 2, 1 }; // Given an array
int k = 2; // given an integer k
// Create a variable 'res' to store minimize cost by calling the function "calculateMinimizeCost"
int res = calculateLowestCost(n, array, k);
cout<< "Minimize Cost for the Given array is " ;
cout << res ;
return 0;
}
輸出
Minimize Cost for the Given array is 6
時間和空間複雜度
上面程式碼的時間複雜度為 O(N * (logN))，因為我們遍歷陣列並使用 sort 函式。
上面程式碼的空間複雜度為 O(1)，因為沒有使用額外的空間來儲存任何內容。
其中 N 是給定陣列的大小。
結論
在本教程中，我們實現了一個 C++ 程式，用於透過將給定陣列拆分為大小為 K 的子集並將每個子集中的最高 K/2 個元素新增到成本中來找到最小化成本。我們實現了一種貪心演算法並使用了 STL 的排序函式。時間複雜度為 O(N * (log N)，其中 N 是給定陣列的大小，空間複雜度為 O(1)，因為不需要額外的空間。
160 次檢視
