使用C++编写，将以下内容翻译为中文：在删除数组的一部分后，计算K个数组的最小公共和

在使用C++数组时，我们有时需要计算多个数组中的最小公共和，同时删除它们后缀的一部分。在本文中，我们将使用C++探讨这个问题的有效解决方案。

语法

让我们首先分析我们选择的方法的语法，然后再继续在我们的代码中实现它 -

int findMinimumCommonSum(vector>& arrays, int suffixToRemove);

算法

这里是解决删除部分数组后缀后求最小公和问题的分步算法 -

• 首先定义函数findMinimumCommonSum，该函数接受两个参数 - arrays，一个表示数组的二维向量，和suffixToRemove，一个表示要从每个数组的后缀中删除的元素数量的整数。

  立即学习“C++免费学习笔记（深入）”；

• 初始化一个变量minimumSum来存储最小公共和，并将其初始值设置为一个较大的值。

• 迭代遍历数组向量中的每个数组。

• 确定当前数组的大小。

• 为了避免以空数组结束，应考虑跳过 suffixToRemove 超过或等于当前数组总大小的迭代。在这种情况下删除所有字符不会产生任何有意义的输出。

• 计算从索引 0 到 size - suffixToRemove - 1 的数组元素之和，并将其存储在变量 currentSum 中。

• 如果currentSum小于minimumSum，则使用currentSum的值更新minimumSum。

• 在遍历所有数组后，minimumSum将包含在删除指定后缀后数组中的最小公共和。

方法 1：暴力破解

在这种方法中，我们将生成要删除的后缀的所有可能组合，并计算每个组合的总和。所有组合中最小的和就是最小公和。

示例

#include 
#include 
#include 
#include 

using namespace std;

int findMinimumCommonSum(vector>& arrays, int suffixToRemove) {
   int minimumSum = INT_MAX;
   int k = arrays.size();

   for (int i = 0; i < k; i++) {
      int size = arrays[i].size();

      if (suffixToRemove >= size)
         continue;

      vector suffix(size, false);
      fill(suffix.begin() + size - suffixToRemove, suffix.end(), true);

      do {
         int currentSum = 0;
         
         for (int j = 0; j < k; j++) {
            int arraySum = 0;
            for (int l = 0; l < size; l++) {
               if (!suffix[l])
                  arraySum += arrays[j][l];
            }
            currentSum += arraySum;
         }

         if (currentSum < minimumSum)
            minimumSum = currentSum;

      } while (next_permutation(suffix.begin(), suffix.end()));
   }

   return minimumSum;
}

int main() {
   vector> arrays = {{1, 2, 3},
                                 {4, 5, 6},
                                 {7, 8, 9}};

   int suffixToRemove = 1;

   int minimumCommonSum = findMinimumCommonSum(arrays, suffixToRemove);

   cout << "Minimum Common Sum: " << minimumCommonSum << endl;

   return 0;
}

输出

Minimum Common Sum: 27

说明

在暴力法中，我们的目标是找到在从它们的后缀中移除指定数量的元素后，多个数组之间的最小公共和。该方法涉及生成所有可能的要移除的后缀的组合，并计算每个组合的和。所有组合中的最小和将是最小公共和。

为了实现这种方法，我们定义了一个名为 findMinimumCommonSum 的函数，它接受两个参数：数组（表示数组的 2D 向量）和 suffixToRemove（表示要从每个数组后缀中删除的元素数量的整数）。

Revid AI

AI短视频生成平台

下载

在函数内部，我们初始化一个变量minimumSum来存储最小的公共和，初始值设置为int类型的最大可能值。然后我们遍历数组向量中的每个数组。对于每个数组，我们确定其大小并检查suffixToRemove值是否小于大小。

如果条件满足，我们使用布尔向量生成所有可能的后缀组合。我们将最后suffixToRemove个元素填充为true，其余元素填充为false。对于每个数组，我们确定其大小，并检查suffixToRemove值是否小于大小。

我们通过计算与后缀向量中的假指示符对应的数组值的总和来进行处理，对于每个组合。我们针对所有数组重复此过程，相应地更新currentSum。

最后，我们将currentSum与minimumSum进行比较，如果currentSum较小，则更新minimumSum。在遍历所有数组和组合之后，minimumSum将包含在删除指定后缀后的最小公共和。

方法2：高效排序

在这种方法中，我们将按非递减顺序对数组进行排序，并计算每个数组的前size - suffixToRemove个元素的总和。所有数组中的最小总和将是最小公共总和。

示例

#include 
#include 
#include 
#include 

using namespace std;

int findMinimumCommonSum(vector>& arrays, int suffixToRemove) {
   int minimumSum = INT_MAX;
   int k = arrays.size();

   for (int i = 0; i < k; i++) {
      int size = arrays[i].size();

      if (suffixToRemove >= size)
         continue;

      sort(arrays[i].begin(), arrays[i].end());

      int currentSum = 0;
      for (int j = 0; j < size - suffixToRemove; j++)
         currentSum += arrays[i][j];

      if (currentSum < minimumSum)
         minimumSum = currentSum;
   }

   return minimumSum;
}

int main() {
   vector> arrays = {{1, 2, 3},
                                 {4, 5, 6},
                                 {7, 8, 9}};

   int suffixToRemove = 1;

   int minimumCommonSum = findMinimumCommonSum(arrays, suffixToRemove);

   cout << "Minimum Common Sum: " << minimumCommonSum << endl;
   
   return 0;
}

输出

Minimum Common Sum: 3

说明

在高效排序方法中，我们的目标是在从后缀中删除指定数量的元素后找到多个数组之间的最小公和。这种方法利用了这样一个事实：对数组进行排序可以简化最小和的计算。

为了实现这种方法，我们定义了一个名为 findMinimumCommonSum 的函数，它接受两个参数：数组（表示数组的 2D 向量）和 suffixToRemove（表示要从每个数组后缀中删除的元素数量的整数）。

在函数内部，我们初始化一个变量minimumSum来存储最小的公共和，初始值设置为int类型的最大可能值。然后我们遍历数组向量中的每个数组。对于每个数组，我们确定其大小并检查suffixToRemove值是否小于大小。

当满足了这个先决条件后，我们的下一步之一将是按升序排列我们数组中的所有个别组件；这种方法主要有助于确保较小的对象位于其初始部分，以提高排列和可读性。

接下来，我们计算排序数组中前 size - suffixToRemove 个元素的和。这对应于从后缀中删除指定数量的元素。我们相应地更新 currentSum。

最后，我们将currentSum与minimumSum进行比较，如果currentSum较小，则更新minimumSum。在遍历所有数组之后，minimumSum将包含在删除指定后缀后的最小公共和。

这种方法非常高效，因为它不需要像暴力方法那样生成和迭代所有可能的组合。相反，它利用排序属性来简化最小和的计算，从而提高性能。

结论

在本文中，我们探讨了一种在C++中找到K个数组中最小公共和的高效方法，该方法在删除它们的后缀的一部分后进行。我们讨论了两种方法-暴力法和高效排序法。暴力法涉及生成所有后缀的组合，而高效排序法对数组进行排序并计算前几个元素的和。根据数组的大小和要删除的后缀元素的数量，高效排序法通常更高效。通过在C++程序中实现这些方法，您可以轻松地从多个数组中找到最小的公共和，并且能够高效地处理后缀的删除。