題目鏈接
看了看其他大佬的文章，為什么要控制右端呢
其實就是一個很簡單的模擬佇列趴，，，
難點就在于根據題意我們可以分析得一段合法區間內，不同種類個數不能超過k+2
哦當然，由于種類數范圍過大，要對種類進行離散化，可以使用STL的map
剩下的就是模擬了,詳見代碼：
#include<bits/stdc++.h> using namespace std; map<int,int> f; int ty,tot,k,n,ans; int type[100010]; int num[100010]; int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ //輸入+離散化 scanf("%d",&ty); if(f[ty]) type[i]=f[ty]; //出現過的給原來的編號 else type[i]=++tot,f[ty]=tot; //沒出現的更新編號并記錄 } int cnt=1,head=1;num[type[1]]++; for(int i=2;i<=n;i++){ while(cnt>=k+2){ //當區間內種類數量大于k+2時左端點右移直到個數小于k+2 num[type[head]]--; if(num[type[head]]==0) //當一個種類數量減為零，區間內種類減一 cnt--; head++; } if(!num[type[i]]) cnt++; //更新 num[type[i]]++; ans=max(ans,num[type[i]]); //用當前種類更新 } printf("%d",ans); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/91727.html
標籤：C++
上一篇：Delphi + sqlite + UniDAC 如何執行一次執行多條update陳述句？
下一篇：C++ 01 基礎知識點