将给定数组拆分为大小为 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.
Cost = 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 的子集k
使用 while 循环将 j 个元素添加到 minimizeCost 中，并减少 j、tempK 和 i。
通过从 i 中减去剩余的 tempK 来更新大小为 k 的子集的 i。
返回 minimzeCost
为了更好地理解上述方法，我们来看下面的代码。
示例
#include <bits/stdc++.h>
using namespace std;
// 创建函数"calculateLowestCost"
int calculateLowestCost( int n, int array [], int k ) {
// 创建变量"minimizeCost"用于存储最终成本
int minimalCost = 0;
// 使用 STL 函数 sort 对数组进行排序
sort(array , array + n);
// 创建变量 updateK 用于存储 k/2 的上限值
int updateK = ceil (k/2.0);
// 使用 for 循环从末尾遍历数组，因为我们需要添加 k/2
// 每个大小为 k 的子集的最高元素
for ( int i = n-1; i >= 0; i-- ) {
// 将 k/2 的 ceil 存储到变量 j
int j = updateK;
// 将 k 存储到 tempK 以维护大小为 k 的子集
int tempK = k;
// 遍历 while 循环，将 k/2 的 ceil 添加到大小为 k 的子集的最高元素
while ( i>=0 && j--){
minimizeCost += array[i];
tempK --;
i--;
}
// 更新 i 为大小为 k 的子集
if(tempK){
i -= tempK;
}
i++;
}
// Return Final cost
return minimizeCost;
}
int main(){
int n = 4; // 给定数组的大小
int array [] = { 3, 4, 2, 1 }; // 给定一个数组
int k = 2; // 给定一个整数 k
// 调用函数"calculateMinimizeCost"创建一个变量"res"来存储最小化成本
int res = calculateLowestCost(n, array, k);
cout<< "最小化给定数组的成本是 " ;
cout << res ;
return 0;
}
输出
最小化给定数组的成本是 6
时间和空间复杂度
上述代码的时间复杂度为 O(N * (logN))，因为我们遍历了数组并使用了排序函数。
上述代码的空间复杂度为 O(1)，因为没有使用额外的空间来存储任何内容。
其中 N 是给定数组的大小。
结论
在本教程中，我们实现了一个 C++ 程序，通过将给定数组拆分为大小为 K 的子集，并将每个子集的最高 K/2 个元素添加到成本中，来查找最小化成本。我们实现了贪婪方法并使用了 STL 的排序函数。时间复杂度为 O(N * (log N))，其中 N 是给定数组的大小，空间复杂度为 O(1)，不需要额外的空间。
