通过将给定数组拆分为大小为 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)，因为不需要额外的空间。