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

Question

The problem is from a programming competition.

给你两个长度相同的序列 A (a1, a2, a3, ... an) 和 B (b1, b2, b3, ... bn) N。在每个步骤中，您可以设置 ai = ai - bi if 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

在我看来有两种解决方法。

具有一定逻辑的迭代算法（我将在 Python 中实现）
你可以使用集合（感觉有点作弊）。

作者可能想让你做的方式：

每次我们都会尝试与列表中的所有其他项目一起达到列表的最小值（或更低）。如果所有项目都相同，我们停止并且 return 成功，否则我们继续前进。如果某些项目低于 0，我们将停止。

import math

num_of_nums = int(input())

a_s = list(map(int, input().split()))
b_s = list(map(int, input().split()))

operations = 0
m = min(a_s)
while not all([a_s[0] == tmp for tmp in a_s]):
    if m < 0:
        print(-1)
        exit(0)
    for i, (a, b) in enumerate(zip(a_s, b_s)):
        if b == 0 and m != a:
            print(-1)
            exit(0)
        elif b == 0 and m == a:
            continue

        operations_to_min = int(math.ceil((a - m) / b))
        operations += operations_to_min
        a_s[i] = a - operations_to_min * b
    m = min(a_s)
print(operations)

设置方式：

读取输入后，我们创建了一组数字，这些数字可以通过从 a 减少每个 b 来创建，因此对于提供的示例，我们得到：

[{1, 3, 5}, {1, 3, 5, 7},...

现在我们找到交集，并从中取出最大的数。
找到这个数字后，我们计算每个 a 和 b 对达到该数字的操作数。

import functools
num_of_nums = int(input())

a_s = list(map(int, input().split()))
b_s = list(map(int, input().split()))

sets = [set([a - b * i for i in range(a // b + 1 if b > 0 else 1)]) for a, b in zip(a_s, b_s)]
res = functools.reduce(lambda a, b: a & b, sets)

if len(res) > 0:
    biggest_num = max(res)
    operations = 0
    for a, b in zip(a_s, b_s):
        if b > 0:
            operations += (a - biggest_num) // b
    print(operations)
else:
    print(-1)

Answer 2

目标不能大于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('');
}

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

How to compute minimum number of operation required to make all the elements of sequence equal to each other

algorithm

discrete-mathematics