最小化增量或减量的成本 以使相同的索引元素成为彼此的倍数

Question

给定两个由 N 个整数组成的数组A [] 和 B [] ，任务是将增加或减少数组元素的总成本减1 ，以使得对于每个^第i^个元素， A [i] 都是 B [的倍数] i] ，反之亦然。

Input: A[] = {3, 6, 3}, B[] = {4, 8, 13}
Output: 4
Explanation:
Incrementing A[0] by 1 (3 + 1 = 4) makes it multiple of B[0](= 4).
Incrementing A[1] by 2 (6 + 2 = 8) makes it a multiple of B[1](= 8).
Decrementing B[2] by 1 (13 – 1 = 12) makes it a multiple of A[2](= 3).
Therefore, the total cost = 1 + 2 + 1 = 4.

Input: A[] = {13, 2, 31, 7}, B[] = {6, 8, 11, 3}
Output: 4

方法：可以贪婪地解决给定的问题。请按照以下步骤解决问题：

• 初始化一个变量，例如 cost ，以存储所需的最低成本。
• 同时遍历数组A []和B []并执行以下步骤：
  • 情况 1：找出更新A [i]使其成为B [i]的倍数的成本，这是(B [i]％A [i])和(A [i] – B [i]的最小值％A [i]) 。
  • 情况 2：找出更新B [i]使其成为A [i]的倍数的成本，这是(A [i]％B [i])和(B [i] – A [i]的最小值％B [i]) 。
  • 将上述两个成本中的最小值添加到每个数组元素的可变成本中。
• 完成上述步骤后，打印成本值作为结果。

下面是上述方法的实现：

C++

// C++ program for the above approach
#include 
using namespace std;
 
// Function to find the minimum cost to
// make A[i] multiple of B[i] or
// vice-versa for every array element
int MinimumCost(int A[], int B[],
        int N)
{
  // Stores the minimum cost
  int totalCost = 0;
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
 
    // Case 1: Update A[i]
    int mod_A = B[i] % A[i];
    int totalCost_A = min(mod_A,
                A[i] - mod_A);
 
    // Case 2: Update B[i]
    int mod_B = A[i] % B[i];
    int totalCost_B = min(mod_B,
                B[i] - mod_B);
 
    // Add the minimum of
    // the above two cases
    totalCost += min(totalCost_A,
             totalCost_B);
  }
 
  // Return the resultant cost
  return totalCost;
}
 
// Driver Code
int main()
{
  int A[] = { 3, 6, 3 };
  int B[] = { 4, 8, 13 };
  int N = sizeof(A) / sizeof(A[0]);
 
  cout << MinimumCost(A, B, N);
 
  return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to find the minimum cost to
// make A[i] multiple of B[i] or
// vice-versa for every array element
static int MinimumCost(int A[], int B[], int N)
{
   
  // Stores the minimum cost
  int totalCost = 0;
 
  // Traverse the array
  for(int i = 0; i < N; i++)
  {
     
    // Case 1: Update A[i]
    int mod_A = B[i] % A[i];
    int totalCost_A = Math.min(mod_A,
              A[i] - mod_A);
 
    // Case 2: Update B[i]
    int mod_B = A[i] % B[i];
    int totalCost_B = Math.min(mod_B,
              B[i] - mod_B);
 
    // Add the minimum of
    // the above two cases
    totalCost += Math.min(totalCost_A,
                totalCost_B);
  }
 
  // Return the resultant cost
  return totalCost;
}
 
// Driver Code
public static void main(String[] args)
{
  int A[] = { 3, 6, 3 };
  int B[] = { 4, 8, 13 };
  int N = A.length;
 
  System.out.print(MinimumCost(A, B, N));
}
}
 
// This code is contributed by souravmahato348

Python3

# Python program for the above approach
 
# Function to find the minimum cost to
# make A[i] multiple of B[i] or
# vice-versa for every array element
def MinimumCost(A, B, N):
   
  # Stores the minimum cost
  totalCost = 0
   
  # Traverse the array
  for i in range(N):
     
    # Case 1: Update A[i]
    mod_A = B[i] % A[i]
    totalCost_A = min(mod_A, A[i] - mod_A)
     
    # Case 2: Update B[i]
    mod_B = A[i] % B[i]
    totalCost_B = min(mod_B, B[i] - mod_B)
     
    # Add the minimum of
    # the above two cases
    totalCost += min(totalCost_A, totalCost_B)
     
  # Return the resultant cost
  return totalCost
 
# Driver Code
A = [3, 6, 3]
B =  [4, 8, 13]
N = len(A)
 
print(MinimumCost(A, B, N))
 
# This code is contributed by shubhamsingh10

C#

// C# program for the above approach
using System;
 
class GFG {
 
  // Function to find the minimum cost to
  // make A[i] multiple of B[i] or
  // vice-versa for every array element
  static int MinimumCost(int[] A, int[] B, int N)
  {
 
    // Stores the minimum cost
    int totalCost = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Case 1: Update A[i]
      int mod_A = B[i] % A[i];
      int totalCost_A = Math.Min(mod_A, A[i] - mod_A);
 
      // Case 2: Update B[i]
      int mod_B = A[i] % B[i];
      int totalCost_B = Math.Min(mod_B, B[i] - mod_B);
 
      // Add the minimum of
      // the above two cases
      totalCost += Math.Min(totalCost_A, totalCost_B);
    }
 
    // Return the resultant cost
    return totalCost;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] A = { 3, 6, 3 };
    int[] B = { 4, 8, 13 };
    int N = A.Length;
 
    Console.Write(MinimumCost(A, B, N));
  }
}
 
// This code is contributed by rishavmahato348

输出：

4

时间复杂度： O(N)
辅助空间： O(1)