一开始一脸懵逼。。
后来才想到维护一左一右俩指针l和r..表示[l,r]这段内不同种类的数字<=k+1种。
显然最左的、合法的l随着r的增加而不减。
顺便离散化，记一下各个种类数字出现的次数就可以算出答案了。
时间复杂度O(n)
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=1e5+233; 7 struct zs{int v,id;}a[maxn]; 8 int mp[maxn],sm[maxn]; 9 int i,j,n,m,ans,num,K; 10 11 int ra;char rx; 12 inline int read(){ 13 rx=getchar(),ra=0; 14 while((rx<'0'||rx>'9'))rx=getchar(); 15 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 16 } 17 bool cmp(zs a,zs b){return a.v<b.v;} 18 inline void add(int x){num+=!sm[x]++;} 19 inline void del(int x){num-=!--sm[x];} 20 int main(){ 21 n=read(),K=read(); 22 for(i=1;i<=n;i++)a[i].v=read(),a[i].id=i; 23 sort(a+1,a+1+n,cmp);int cnt=0; 24 for(i=1;i<=n;mp[a[i].id]=cnt,i++) 25 if(a[i].v!=a[i-1].v||i==1)cnt++; 26 int l=1,r=1;sm[mp[1]]++,num=ans=1; 27 for(r=2;r<=n;r++){ 28 add(mp[r]); 29 while(num>K+1)del(mp[l]),l++; 30 ans=max(ans,sm[mp[r]]); 31 // printf("%d--%d ",l,r); 32 } 33 printf("%d ",ans); 34 }