Written in C++, translate the following into Chinese: Calculate the minimum common sum of K arrays after deleting part of the array

When using C arrays, we sometimes need to calculate the minimum common sum among multiple arrays while removing part of their suffixes. In this article, we will explore an efficient solution to this problem using C.

grammar

Let's first analyze the syntax of our chosen method before proceeding to implement it in our code -

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

algorithm

Here is a step-by-step algorithm to solve the problem of finding the least common sum after deleting part of the array suffix -

• First define the function findMinimumCommonSum, which accepts two parameters - arrays, a two-dimensional vector representing the array, and suffixToRemove, an integer representing the number of elements to be removed from the suffix of each array.

• Initialize a variable minimumSum to store the minimum common sum, and set its initial value to a larger value.

• Iterate through each array in the array vector.

• Determine the size of the current array.

• To avoid ending up with an empty array, you should consider skipping iterations of suffixToRemove that are greater than or equal to the total size of the current array. Removing all characters in this case does not produce any meaningful output.

• Calculate the sum of array elements from index 0 to size - suffixToRemove - 1 and store it in the variable currentSum.

• If currentSum is less than minimumSum, use the value of currentSum to update minimumSum.

• After traversing all arrays, minimumSum will contain the smallest common sum in the array after removing the specified suffix.

Method 1: Brute force cracking

In this approach we will generate all possible combinations of the suffixes to be removed and calculate the sum for each combination. The smallest sum among all combinations is the least common sum.

Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int findMinimumCommonSum(vector<vector<int>>& 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<bool> 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<vector<int>> 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;
}

Output

Minimum Common Sum: 27

illustrate

In the brute force method, our goal is to find the smallest common sum between multiple arrays after removing a specified number of elements from their suffixes. The method involves generating all possible combinations of the suffixes to be removed and calculating the sum of each combination. The smallest sum among all combinations will be the smallest common sum.

To implement this approach, we define a function called findMinimumCommonSum, which accepts two parameters: an array (a 2D vector representing the array) and suffixToRemove (an integer representing the number of elements to be removed from each array suffix) ).

Inside the function, we initialize a variable minimumSum to store the minimum common sum, and the initial value is set to the maximum possible value of type int. Then we iterate through each array in the array vector. For each array, we determine its size and check if the suffixToRemove value is less than the size.

If the conditions are met, we use a Boolean vector to generate all possible suffix combinations. We fill the last suffixToRemove elements with true and the remaining elements with false. For each array, we determine its size and check if the suffixToRemove value is less than the size.

We proceed by computing the sum of the array values ​​corresponding to the false indicators in the suffix vector, for each combination. We repeat this process for all arrays, updating currentSum accordingly.

Finally, we compare currentSum with minimumSum, and if currentSum is smaller, update minimumSum. After iterating through all arrays and combinations, minimumSum will contain the minimum common sum after removing the specified suffix.

Method 2: Efficient sorting

In this method, we will sort the arrays in non-decreasing order and calculate the sum of the first size - suffixToRemove elements of each array. The smallest sum among all arrays will be the smallest common sum.

Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int findMinimumCommonSum(vector<vector<int>>& 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<vector<int>> 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;
}

Output

Minimum Common Sum: 3

illustrate

In efficient sorting method, our goal is to find the minimum common sum between multiple arrays after removing a specified number of elements from the suffix. This approach takes advantage of the fact that sorting the array simplifies the calculation of the minimum sum.

To implement this approach, we define a function called findMinimumCommonSum, which accepts two parameters: an array (a 2D vector representing the array) and suffixToRemove (an integer representing the number of elements to be removed from each array suffix) ).

Inside the function, we initialize a variable minimumSum to store the minimum common sum, and the initial value is set to the maximum possible value of type int. Then we iterate through each array in the array vector. For each array, we determine its size and check if the suffixToRemove value is less than the size.

When this prerequisite is met, one of our next steps will be to sort all the individual components in our array in ascending order; this approach mainly helps to ensure that smaller objects are in their initial section to improve the sorting and readability.

Next, we calculate the sum of the first size - suffixToRemove elements in the sorted array. This corresponds to removing the specified number of elements from the suffix. We update currentSum accordingly.

Finally, we compare currentSum with minimumSum, and if currentSum is smaller, update minimumSum. After iterating through all arrays, minimumSum will contain the minimum common sum after removing the specified suffix.

This method is very efficient because it does not require generating and iterating all possible combinations like brute force methods. Instead, it exploits the ordering properties to simplify the calculation of the minimum sum, thus improving performance.

in conclusion

In this article, we explore an efficient way to find the smallest common sum among K arrays in C, after removing part of their suffixes. We discussed two methods - brute force and efficient sorting. The brute force method involves generating all combinations of suffixes, while the efficient sort method sorts the array and calculates the sum of the first few elements. Depending on the size of the array and the number of suffix elements to be removed, efficient sort is usually more efficient. By implementing these methods in a C program, you can easily find the smallest common sum from multiple arrays and handle the removal of suffixes efficiently.

The above is the detailed content of Written in C++, translate the following into Chinese: Calculate the minimum common sum of K arrays after deleting part of the array. For more information, please follow other related articles on the PHP Chinese website!