algorithm - 两个序列和具有相同模块的最小步骤

Question

我想要一个解决这个问题的方法。
我们有两个整数序列 a[1...n] 和 b[1...n]。每次我们都可以从 a[1...n] 中选择一个子序列(连续元素)，然后将 x (任意数)添加到所有子序列中。我们的目标是在最少的步骤中，对于每个 i:a[i] = b[i](模块 5)
(5是问题标题中m的例子)
限制:

1 <= n <= 10^6
1 <= a[i],b[i] <= 10^9

例如:
一 = 1 2
b = 3 4
最少:1
有没有可能给我一个解决它的方法？谢谢。

Answer 1

问题重述

• 我们有两个整数数组 a 和 b，长度相同 n。
• 我们有一个模数m； m = 5 在你的例子中。
• 我们的目标是改变 a 的值，使得所有 i 的 (a[i] - b[i]) % m == 0 。
• 我们希望以最少的步数达到目标。
• 在每个步骤中，我们将任意整数x 添加到a[i] 到a[j] 的所有连续元素。
• 关于我们可以为每个步骤进行多少计算，没有任何说明。我们会尽量减少它，但如果我们必须花费二次、三次甚至阶乘时间，那似乎是允许的。

分析

首先，观察到我们可以通过将所有 b 值设置为零并将 a[i] 的每个值调整为 (a[i] - b[i]) % m.然后我们就忽略b，我们只考虑a的取模m，目标变成“a中的所有值” code> 必须为零”。例如:

m = 5
a = [1234, 5678, 9012, 3456]
b = [3141, 2718, 1414, 4242]

简化为:

a = [3, 0, 3, 4]

显然，我们可以通过简单地单独更改每个非零值来达到目标​​。我们可以改进吗？有时。例如，这可以分两步解决:

a = [2, 2, 2, 2, 0, 3]

一个稍微复杂的例子需要四个步骤:

a = [2, 1, 2, 2, 1, 2, 0, 3]
   + 3, 3, 3, 3, 3, 3
a = [0, 4, 0, 0, 4, 0, 0, 3]
   do the rest individually

据我所知，每当我们有一系列以相同数字开头和结尾的数字时，将它们全部更改为将端点归零不会受到惩罚:

a = [..., 3, ?, ?, ?, ?, ?, ?, 3, ...]
   +      2, 2, 2, 2, 2, 2, 2, 2
a = [..., 0, ?, ?, ?, ?, ?, ?, 0, ...]

这一步将两个数字归零。中间的数字不会更糟，除非它们全为零，即使那样，总步数也是两种方式。

算法

虽然我无法严格证明它，但这是一个看起来非常理想的算法:

range = entire array
while true:
    move endpoints inward to skip zeroes
    if endpoints pass each other:
        everything is zero, halt
    if endpoints have equal value X:
        add (5 - X) % m to range, which will zero out endpoints
        loop
    (endpoints are unequal)
    for each endpoint:
        identify the "run" of equal numbers R at the endpoint
          (might be just one)
        skip any zeroes after the run ("after" means "inward")
        identify the next number N after the run and zeroes
    if N of endpoint x equals R of endpoint y:
        zero out the run at endpoint x
        this will set up an advantageous equal-endpoint in next step
        loop
    (neither N equaled opposite R)
    zero out whichever run is longer
    loop

例子

让我们将其应用于上面的示例数据，看看它是如何工作的。

a = [2, 1, 2, 2, 1, 2, 0, 3]

range = 2 1 2 2 1 2 0 3
no zeroes to skip at ends
unequal endpoints
left run: R = 2, N = 1
right run: R = 3, N = 2
N of right run = R of left run
zero out right run
range = 2 1 2 2 1 2 0 0
steps = 1
loop

range = 2 1 2 2 1 2 0 0
skip zeroes
range = 2 1 2 2 1 2
equal endpoints
add 3 to range
range = 0 4 0 0 4 0
steps = 2
loop

range = 0 4 0 0 4 0
skip zeroes
range = 4 0 0 4
equal endpoints
add 1 to range
range = 0 1 1 0
steps = 3
loop

range = 0 1 1 0
skip zeroes
range = 1 1
equal endpoints
add 4 to range
range = 0 0
steps = 4
loop

range = 0 0
skip zeroes
endpoints passed each other
halt

该算法按照预期采取了 4 个步骤。