0

如果您有three or more numbers一个除法参数，那么您必须以最少的操作次数来均衡数组元素。您可以通过仅从除法参数中划分数组元素来均衡元素。

示例 1：向量 arr{64,32,16}; 除法参数=2。最低数量 的操作是 3。

解释：64除以2两次，32除以2一次。所以最小操作是 2+1=3。

示例 2：向量 arr{64,33,25}; 除法参数=2。最低数量 的操作是 15。

说明：对于最小数量。在操作中，您必须除以 64（6 次）、33（5 次）、25（4 次）。这样三个元素都变为 1 。

除法参数是用户给定的。向量数组及其大小也是用户给定的

总是有整数除法例如：33/2=16。

请帮助我以有效的方式解决此查询。

4

1 回答 1

3

在您纠正问题以澄清除法是整数除法之前，我首先想到的是 GCD。

现在，我想出了两种算法

算法1：

  1. 取最大数，除以第二大，或等于第二大，每次除法增加计数器
  2. 如果它变成第二大，再次重复上述步骤。
  3. 如果它等于第 2 大，则开始将其与第 3 大进行比较，但现在，将计数器每除法一次（因为有 2 个相等的最大数），然后重复上述步骤。

前任 -

[64,32,17,36], div factor = 2, counter(ctr) = 0
64 -> 32, [32,32,17,36] steps = 1, ctr = 1
36 -> 18, [32,32,17,18] steps = 1, ctr = 2
32 -> 16, [16,16,17,18] steps = 1*2(as 2 values = 32) = 2, ctr = 4
18 -> 9, [16,16,17,9] steps = 1, ctr = 5
17 -> 8, [16,16,8,9] steps = 1, ctr = 6
16 -> 8, [8,8,8,9] steps = 1*2(as 2 values = 16) = 2, ctr = 8
9 -> 4, [8,8,8,4] steps = 1, ctr = 9
8 -> 4, [4,4,4,4] steps = 1*3(as 3 values = 8) = 3, ctr = 12

所以最小步数是 12。 (64 -> 4, 32 -> 3, 17 -> 2, 36 -> 3) = 4 + 3 + 2 +3 = 12

算法 2（更好）

  1. 从均衡对开始，从左到右移动。
  2. 随着左数的每一个除法，计数器增加右数的索引（或左数的索引+1）
  3. 每除以正确的数字，计数器加 1
  4. 继续直到你到达最后一对。

前任 -

[64,32,17,36], div factor 2, counter (ctr) = 0
(64,32),17,36 -> (32,32),17,36 => steps = 1*1 = 1, ctr = 1
32,(32,17),36 -> 8,(8,8),36 => steps = 2*2 + 1 = 5, ctr = 6
8,8,(8,36) -> 8,8,(4,4) => steps = 1*3 + 3 = 6, ctr = 12

答案 = 12

于 2020-06-21T19:50:29.180 回答