【jzoj3464】秀姿势

题目描述

“蓝猫淘气三千问，看蓝猫，我有姿势我自豪！”话说能考上HYSBZ的孩纸们肯定都是很有姿势的孩纸们，但是大家普遍偏科，都只有一门科目考得好。已知HYSBZ的入学考试科目数量小于等于10^9，而有n个学生参加了入学考试。

现在HYSBZ要刷人了，招生办每一次刷人会把一个科目考得好的人全部刷掉，但是最多不能刷超过K次。（刷就是不录取）而HYSBZ的校长看录取名单时，最喜欢看的就是连续都是同一个科目考得好的人。

他定义完美学生序列为连续且考得好的科目都为同一门的学生序列。现在招生办主任想让你帮他设计一种录取方案，使得最长的完美学生连续子序列尽量长。

输入

共 N+1 行，第一行 2 个正整数 n，K，n 表示入学考试人数，K 表示刷人次数上限。

接下来 N 行，每行仅一个正整数 A i ，为 i 号学生所考得好的科目。

输出

仅 1 个正整数，为最长的最长完美学生序列。

样例输入

9 1
2
7
3
7
7
3
7
5
7

样例输出

4

题解

队列。任意时刻，只需保证队列里只有 k+1 种科目，然后用队列里科目的众数去更新答案。

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn=100000+50;
int n,k,a[maxn],cnt[maxn],tot,maxx;
int ls[maxn],ans,l;
templatevoid read(T& aa){
char cc; ll ff;aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
int main(){
// freopen("sugata.in","r",stdin);
// freopen("sugata.out","w",stdout);
read(n),read(k);
for(int i=1;i<=n;i++) read(a[i]),ls[++ls[0]]=a[i];
sort(ls+1,ls+1+ls[0]);
int sz=unique(ls+1,ls+ls[0]+1)-ls;
for(int i=1;i<=n;i++) a[i]=lower_bound(ls+1,ls+sz+1,a[i])-ls;
for(int r=1;r<=n;r++){
++cnt[a[r]];
if(cnt[a[r]]==1) tot++;
while(tot>k+1){
--cnt[a[l]];
if(cnt[a[l]]==0) tot--;
l++;
}
ans=max(ans,cnt[a[r]]);
}
cout< return 0;
}