题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3048
STL大法好！
根据题意，可以看出我们要找的就是一个尽可能长的包含<=k+1种数的子序列
所以我们用一个队列扫一遍就好，当队列里的数的种类>k+1了，就从队头开始弹出，每有一个数新加入队列时，统计下答案就可以了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<bits/stdc++.h> using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m,ans,num; map<int,int>mp; queue<int>q; int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++){ int x=rd(); if(mp[x]==0){ while(num>m){ int t=q.front(); q.pop(); mp[t]--; if(mp[t]==0)num--; } num++; } mp[x]++; q.push(x); ans=max(ans,mp[x]); } printf("%d\n",ans); return 0; } |
