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

Question

The problem is from a programming competition.

你有两个序列 A (a1, a2, a3, ... an) 和 B (b1, b2, b3, ... bn)，它们的长度相同为 N。在每一步操作中，如果 ai >= bi，则可以将 ai 设为 ai - bi。确定将所有数变为相等的最小步骤数。 例如：

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

在上面的例子中，使所有元素相等所需的最小步骤数为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的所有元素相等。

有人能帮我解决如何高效地解决这个问题吗？

- strikersps

---

问题陈述：https://www.hackerearth.com/practice/basic-programming/input-output/basics-of-input-output/practice-problems/algorithm/make-all-equal-90a21ab2/description/ - strikersps

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)

集合方法：

读取输入后，我们创建了一个数字集合，该集合可以通过从每个b减去a来生成，因此对于提供的示例，我们得到：

[{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)

- Yonlif

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('');
}

- גלעד ברקן

---

感谢您提供的逻辑。然而，在实现过程中，存在一个小错误，即除以零。您可以添加另一个条件来减轻这个错误，即 if(t == A[i]) continue。 - strikersps

@strikersps，这个修复无法解决如果B[i]为零的情况。据我所知，我们可以有0 mod x, x != 0，它就是零。也就是说，如果t - A[i]等于零，只要模数为正，我们仍然可以进行模运算检查。 - גלעד ברקן

@strikersps 说过，这个实现中缺少处理 B[i] == 0 的部分。 - גלעד ברקן

@strikersps true -- 我们允许 B[i] 为零且仍然有效的条件是 t == A[i]。很好的发现。 - גלעד ברקן

谢谢，我已经在 python 中实现了解决方案，你可以在这里查看：https://github.com/strikersps/Competitive-Programming/blob/master/Hacker-Earth/Number-of-Steps/number_of_steps.py - strikersps