C++ 通过将给定的数组拆分为大小为K的子集，并将每个子集的最高K/2个元素添加到成本中，以最小化成本

拆分数组意味着我们需要将数组分割成子集。在这个问题中，我们给定了一个大小为n的整数数组和一个整数k，我们的目标是通过将整个给定的数组拆分为大小为k的子集，并将每个子集的最高k/2个元素添加到成本中来计算最低成本。

注意：我们这里考虑k/2的上限。

让我们看看下面的示例和解释，以更好地理解问题。

示例例子

输入

n: 4
array: [ 3, 4, 2, 1 ]
k: 2

输出

说明：我们在这里将给定的数组拆分为[ 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

输出

解释：在这里，我们将给定的数组分为 [ 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;
}