长度为 n 的只包含0 和 1 的序列,你可以对它进行多次操作。在每次操作中,你都可以选择一个数字 0 变成 1, 或者选择一个数字 1 变成 0,使得最终局面满足如下特点: 对于任意相邻的两个 1,它们在序列中的距离都是 d 的倍数,给定 d,求最小操作次数。 长度为 n 的只包含 0 和 1 的序列,每次操作选一个 0 变 1 或者 1 变 0,使得最终局面的相邻的两个 1 之间距离是 d 的倍数,问最小操作次数。
第一行输入两个正整数n, d。 第二行输入 n 个数,表示题目所描述的序列。
输出一个数,表示最小操作次数。
5 2 0 1 0 0 1
1
8 2 1 0 1 0 0 0 1 1
1
【样例1说明】 将任何一个 1 变成 0,这样就没有相邻的 1 了,自然也满足题目要求。
【样例2说明】 将最后一个 1 变成 0,这样序列变为 [1,0,1,0,0,0,1,0],1 的位置分别是 [1,3,7],其中 1 和 3 的距离是 2 的倍数,3 和 7 的距离也是 2 的倍数
对于测试点1:1 ≤ n ≤ 10^5 , d = 1。
对于测试点2~ 3:1 ≤ n ≤ 10^5 , d = 2
对于测试点4~ 5:1 ≤ d ≤ n ≤ 10^3。
对于测试点6~ 10:1 ≤ d ≤ n ≤ 10^5。