原题链接
思路
使用滑动窗口维护当前窗口内各元素的出现次数。当窗口右端扩展导致某个元素出现次数超过 k 时，左端右移直至满足条件。过程中记录最大窗口长度。
标程
n, k = map(int, input().split())
a = list(map(int, input().split()))
from collections import defaultdict
count = defaultdict(int)
left = 0
max_len = 0
for right in range(n):
count[a[right]] += 1
while count[a[right]] > k:
count[a[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
print(max_len)
【AI 提供】数据生成代码
import random
n = random.randint(1, 10**5)
k = random.randint(1, n)
a = [random.randint(1, 10**4) for _ in range(n)]
print(n, k)
print(' '.join(map(str, a)))
【实际上】数据生成代码
import random
from collections import defaultdict
for case in range(1, 11):
n = random.randint(1, (10 ** 5) if (case >= 3) else 100)
k = random.randint(1, n)
a = [random.randint(1, 10**4) for _ in range(n)]
with open(f'b{case}.in', 'w') as f:
f.write(f'{n} {k}\n{" ".join(map(str, a))}\n')
with open(f'b{case}.ans', 'w') as f:
count = defaultdict(int)
left = 0
max_len = 0
for right in range(n):
count[a[right]] += 1
while count[a[right]] > k:
count[a[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
f.write(str(max_len))
