algorithm - 如何计算使序列的所有元素彼此相等所需的最小操作次数

Question

The problem is from a programming competition.

给你两个序列 A (a1, a2, a3, ... an)和 B (b1, b2, b3, ... bn)相同长度 N .每一步都可以设置 ai = ai - bi如果 ai >= bi .确定生成 A 中所有数字所需的最小步骤数彼此平等。
例如

A = {5, 7, 10, 5, 15} 
B = {2, 2, 1, 3, 5}

在上面的例子中，制作 A 中的所有元素所需的最小步骤数。彼此相等是 8 .

A = {5, 15, 25, 35, 45, 90, 100}
B = {5, 5, 5, 5, 5, 5, 5}

在上面的例子中，制作 A 中的所有元素所需的最小步骤数。彼此相等是 56 .
请注意，如果不可能使序列的所有元素 A相等然后打印 -1 .
例如

A = {5, 6}  
B = {4, 3}

在上述情况下，答案是 -1因为不可能把 A的所有元素都做成彼此平等。

A = {5, 15, 25, 35, 45, 90, 100}
B = {5, 5, 5, 5, 5, 0, 5}

在上述情况下，答案是 -1因为不可能把 A的所有元素都做成彼此平等。
任何人都可以帮助我如何有效地解决这个问题？

Answer 1

目标不能大于 A 中的最小元素.如 m是 A 中最小元素的索引，目标也必须是值 A[m] - k * B[m] 之一(非负整数 k )。由于 A 中可能存在最小元素的重复项，每个都有不同的 b , 为简化起见，我们可以尝试所有等于或小于 min(A) 的目标.
我们在降序循环中尝试它们，因为显然最高有效的将需要最少的步骤才能达到。有效性检查，必须适用于所有 (a, b)对，给定候选目标 t :

(a - t) mod b == 0

例子:

A = {5, 7, 10, 5, 15}
B = {2, 2, 1, 3, 5}

t = 5

a's:

 5: 5 == 5
 7: (7 - 5) mod 2 == 0
10: (10 - 5) mod 1 == 0
 5: 5 == 5
15: (15 - 5) mod 5 == 0

JavaScript 代码:

function f(A, B){
  const n = A.length;
  const m = Math.min(...A);
  let result;
  
  for (let t=m; t>=0; t--){
    result = 0;
    
    for (let i=0; i<n; i++){
      if ((A[i] - t) % B[i] == 0){
        result = result + (A[i] - t) / B[i];
        
      } else {
        result = -1;
        break;
      }
    }
    
    if (result > -1)
      return result;
  }
  
  return result;
}

var ABs = [
  [[5, 7, 10, 5, 15],
   [2, 2, 1, 3, 5]],

  [[5, 6],
   [4, 3]]
];

for (let [A, B] of ABs){
  console.log(`A: ${ A }`);
  console.log(`B: ${ B }`);
  console.log(f(A, B));
  console.log('');
}