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

Question

The problem is from a programming competition.

给定两个序列A（a1， a2， a3，... an）和B（b1， b2， b3，... bns），长度相同N。在每个步骤中，您可以设置ai=ai-biifai

例如

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

在我看来，有两种方法可以解决它。

1. 带有一些逻辑的迭代算法（我将用Python实现）
2. 你可以使用集合（感觉像是作弊）

作者可能想让你这样做：

每一次我们都会尝试用列表中的所有其他项目达到列表的最小值（或更低）。如果所有的项目都是相同的，我们停止并返回成功，否则我们继续前进。如果一些项目低于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('');
}