求解使连续k长度子数组和相等的数组最小修改次数

现有n台服务器，第i台服务器的算力为server[i]单位。用户可将k个不同任务分配给任意索引i到i+k-1的连续服务器段。为保证行为一致性，要求所有这类连续子数组的算力和相等，可替换任意服务器为任意算力的新服务器。给定server数组与整数k，求需替换的服务器最小数量。

示例 #

• 示例1：n=4，server=[1,2,3,2]，k=2。原连续子数组和为[3,5,5]，替换第1台为3后，数组变为[3,2,3,2]，子数组和均为5，答案为1。
• 示例2：n=5，server=[1,2,1,1,2]，k=3。原连续子数组和均为4，答案为0。

问题代码 #

以下是一段无法通过第二个测试用例的Java代码：

public static void main(String[] args) {
    System.out.println(solve(2, Arrays.asList(1,2,3,2))); // 正确答案是1
    System.out.println(solve(2, Arrays.asList(1,2,3))); // 正确答案是2
    System.out.println(solve(3, Arrays.asList(1,2,1,1,2))); // 正确答案是0
}

private static int solve(int k, List<Integer> server) {
    // 这段代码无法通过第二个测试用例
    long sum = 0;
    for(int i=0; i<k; i++) sum += server.get(i); // 计算前k个元素的和
    long current = sum; // 赋值给current
    int result = 0;
    int n = server.size();
    for(int i=1; i<=n-k; i++) {
        current += server.get(i+k-1) - server.get(i-1); // 计算以i开头的连续k个元素的和
        if(current != sum) result++; // 发现和不相等则计数加1
        if(current > sum) sum = current; // 如果当前和更大，更新sum
    }
    return result; 
}

这段代码的核心错误在于假设只需要修改单个服务器就能让所有连续子数组和相等，但实际约束条件要严格得多：所有长度为k的连续子数组和相等，意味着服务器数组必须满足特定的周期性规律。

正确解题思路 #

1. 推导核心约束 #

假设所有长度为k的连续子数组和都等于S，那么对于任意i（1 ≤ i ≤ n-k）：
sum(server[i..i+k-1]) = sum(server[i-1..i+k-2])
展开后可推导出：server[i+k-1] = server[i-1]

这意味着数组中下标模k结果相等的元素必须全部相同。比如k=2时，下标0、2、4...的元素要一致，下标1、3、5...的元素要一致。

2. 统计每个分组的最优保留元素 #

对于每个余数r（0 ≤ r < k），收集所有下标i满足i % k == r的元素。要让替换数量最少，我们选择该分组中出现次数最多的元素，保留它，替换掉其他元素。该分组的替换数为分组元素总数 - 该元素出现次数。

3. 计算总替换数 #

将每个模k分组的替换数相加，得到的总和就是需要替换的服务器最小数量。

验证示例 #

• 示例2：n=5，k=3，server=[1,2,1,1,2]
  模3的分组：

  • r=0：下标0、3 → 元素[1,1]，出现最多的是1，替换数0
  • r=1：下标1、4 → 元素[2,2]，出现最多的是2，替换数0
  • r=2：下标2 → 元素[1]，替换数0
    总和为0，符合正确答案。

• 示例1：n=4，k=2，server=[1,2,3,2]
  模2的分组：

  • r=0：下标0、2 → 元素[1,3]，出现最多的元素是1或3，替换数1
  • r=1：下标1、3 → 元素[2,2]，替换数0
    总和为1，符合正确答案。

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