如何计算将0-6取值数组所有元素置为0的最少操作次数？

问题定义 #

给定元素取值范围为0-6（含6）的数组，每次操作可对连续子数组的所有元素加/减同一个值（元素遵循循环取值：如5+3=1，1-2=6，等价于模7运算），求将所有元素置为0的最少操作次数。

错误方法分析 #

直接统计不同数字的出现次数，或仅处理首尾相同元素的方法存在缺陷。例如数组{1,3,2,2,2}，错误方法会认为需要3次操作，但实际仅需2次：

1. 对索引1-4的元素减2（等价于加5），得到{1,1,0,0,0}；
2. 对前两个元素减1（等价于加6），得到全0数组。
   这类错误源于未考虑操作可通过叠加覆盖多个不同的调整需求。

正确解法思路 #

核心是通过差分数组将问题转化为统计操作的“贡献量”，步骤如下：

1. 计算目标调整量：
   对每个元素a[i]，计算将其置为0的调整量d[i]，满足(a[i] + d[i]) ≡ 0 mod7，即：

   d[i] = (7 - a[i] %7) %7
   

2. 构建模7差分数组：
   差分数组diff长度为n+1（n为原数组长度），用于记录相邻元素调整量的变化：

   • diff[0] = d[0] %7
   • 对1 ≤ i ≤n-1：diff[i] = (d[i] - d[i-1]) %7，若结果为负则加7转为0-6的正整数
   • diff[n] = (-d[n-1]) %7，同样确保结果在0-6范围内

3. 计算最少操作次数：
   统计差分数组中所有正元素的和sum_pos，最少操作次数为sum_pos //7。
   原理：每次操作会在差分数组中产生两个正元素（k和7-k），两者之和为7，因此每7的贡献对应一次操作。

示例验证 #

以数组{1,3,2,2,2}为例：

1. 计算d数组：[6,4,5,5,5]
2. 构建差分数组：
   • diff[0] =6
   • diff[1]=(4-6)%7=5
   • diff[2]=(5-4)%7=1
   • diff[3]=(5-5)%7=0
   • diff[4]=(5-5)%7=0
   • diff[5]=(-5)%7=2
3. sum_pos=6+5+1+2=14，操作次数14//7=2，与正确结果一致。

代码实现（Python） #

def min_operations(arr):
    n = len(arr)
    # 检查是否全为0
    all_zero = True
    for num in arr:
        if num !=0:
            all_zero = False
            break
    if all_zero:
        return 0
    
    # 计算d数组
    d = [(7 - num %7) %7 for num in arr]
    
    # 构建差分数组
    diff = [0]*(n+1)
    diff[0] = d[0] %7
    for i in range(1, n):
        val = (d[i] - d[i-1]) %7
        diff[i] = val if val >=0 else val +7
    diff[n] = (-d[-1]) %7
    diff[n] = diff[n] if diff[n] >=0 else diff[n]+7
    
    # 计算sum_pos并返回结果
    sum_pos = sum(x for x in diff if x>0)
    return sum_pos //7

# 测试示例
print(min_operations([1,3,2,2,2])) # 输出2
print(min_operations([1,1,0,0,0])) # 输出1
print(min_operations([0,1,2,3,4,5,6])) # 输出6

内容的提问来源于stack exchange，提问作者Kacper