题解 P3069 【[USACO13JAN]Cow Lineup G】

2-pointer 练习题

根据题意，为了创造连续排列的一段相同类型的牛，我们可以去除掉队列里 k 种血统的奶牛，所以我们的排列里最多只能有 k+1 种奶牛，所以我们可以用两个指针进行扫描，用一个 map 来记录每个类型的数量，将右指针向右移动，并将没有出现过的类型累加到答案之中，当序列中有 k+2 种奶牛时，就要将左指针向右移动直至序列中的奶牛数小于 k+2 。最后取一个右指针代表类型在序列中的数量的最大值即可。

code

#include <cstdio>
#include <algorithm>
#include <map>
#define sf(x) scanf("%d",&x)
#define pf(x) printf("%d
",x)
#define N 100077
using namespace std;

map<int,int>g;
int n,k;
int a[N];

int main(){
	sf(n),sf(k);
	for(int i=1;i<=n;++i) sf(a[i]);
	int l=1,r=0,cnt=0,ans=0;
	while(r<=n){
		if(++g[a[++r]]==1) cnt++;
		while(cnt==k+2)
			if(!(--g[a[l++]])) cnt--;
		ans=max(ans,g[a[r]]);
	}
	pf(ans);return 0;
}