P3069 [USACO13JAN] Cow Lineup G

题目描述

Farmer John (FJ) 的 $N (1 \le N \le 10^5)$ 只奶牛排成了一队,每只牛都用编上了一个“血统编号”,该编号为范围 $0$ 至 $10^9$ 的整数。血统相同的奶牛有相同的编号,也就是可能有多头奶牛是相同的“血统编号”。 FJ 觉得如果连续排列的一段奶牛有相同的血统编号的话,奶牛们看起来会更具有威猛。为了创造这样的连续段,约翰最多能选出 $k$ 种血统的奶牛,并把他们全部从队列中赶走。 请帮助 FJ 计算这样做能得到的由相同血统编号的牛构成的连续段的长度最大是多少?

输入格式

第 $1$ 行:两个用空格隔开的整数 $N$ 和 $K$。 第 $2$ 到 $1+N$ 行:第 $i+1$ 行包含品种 ID $B(i)$。

输出格式

第 1 行:FJ 能创造出的具有相同品种 ID 的连续奶牛块的最大长度。

说明/提示

有 $9$ 头牛排成一队,品种 ID 分别为 $2, 7, 3, 7, 7, 3, 7, 5, 7$。FJ 希望从这队中移除最多 1 种品种 ID。 通过移除所有品种 ID 为 $3$ 的奶牛,队伍变为 $2, 7, 7, 7, 7, 5, 7$。在这个新的队伍中,有一个由 $4$ 头品种 ID 相同(均为 $7$)的奶牛组成的连续块。