给你一个长度为n(1<=n<=100,000)的自然数数列，其中每一个数都小于等于10亿，现在给你一个k，表示你最多可以删去k类数。数列中相同的数字被称为一类数。设该数列中满足所有的数字相等的连续子序列被叫做完美序列，你的任务就是通过删数使得该数列中的最长完美序列尽量长。
输入格式:
第一行两个整数N,K。
输出格式：最长的完美序列的长度。
想象一个窗口，这个窗口从第s个数开始，第t个数结束，窗口中一共有K+1种数，
那么这个时候对于这个区间的答案就是其中最多的一种数，然后将这个窗口向右移动，换成另外的K+1种数，直到最后。
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int Max=100000; int N,K; int A[Max+5],B[Max+5],cnt[Max+5]; void getint(int &num){ char c;int flag=1;num=0; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();} num*=flag; } int main(){ getint(N),getint(K); for(int i=1; i<=N; ++i){ getint(A[i]); B[i]=A[i]; } sort(B+1,B+1+N); int len=unique(B+1,B+1+N)-B; for(int i=1; i<=N; ++i) A[i]=lower_bound(B+1,B+1+len,A[i])-B; int ink=0,s=1,t=1,Ans=1; while(t<=N){ if(!cnt[A[t]]){ if(ink<=K){ ++cnt[A[t]]; ++ink; } else { while(ink==K+1){ --cnt[A[s]]; if(!cnt[A[s]]) --ink; ++s; } ++cnt[A[t]]; ++ink; } } else { ++cnt[A[t]]; Ans=max(Ans,cnt[A[t]]); } ++t; } printf("%d\n",Ans); return 0; }
