思路:枚举 + 滑动窗口

​ 很容易想到暴力枚举的方法。先枚举最终这段连续相同的数字是什么，再去枚举每个长度为$k$的子段。然后再去计算答案。这样复杂度是$O(10n^2)$的。

​ 我们发现每个子段的答案可以使用滑动窗口的方法动态维护。即往右移动一格就把出去的值给减去，然后再加上就行。复杂度$O(10n)$

代码

python

n , k = list(map(int , input().split()))
a = list(map(int , input().split()))
ans = 10000000000
# 枚举最后变成什么
for d in range (10):
	cost = 0
	# 先求前k个
	for i in range (k):
		cost += abs(a[i] - d)
	ans = min (ans , cost)
	# 滑动窗口
	for i in range (k , n):
		cost += abs(a[i] - d)
		cost -= abs(a[i - k] - d)
		ans = min (ans , cost)

print (ans)

题目内容

小红是一个大学生，他喜欢研究各种关于字符串的问题。有一天，他在研究字符串问题时想到了这个问题。

这道题目给定一个长度为 $n$ ( $n\le 10^5$ )的、由数字字符组成的字符串，你可以进行如下操作： 选择一个字符，使得其加 $1$ 或者减 $1$ 。

请注意,你无法对’0’进行减 $1$ 操作，也无法对’9’进行加 $1$ 操作。

若干次操作后，你需要使得该字符串存在一个长度为 $k$ ( $1\le k\le n$ )的、所有字符都相同的连续子串。请你计算出操作的最小次数。

输入

3 2
1 2 3

输出

1