bzoj3048[Usaco2013 Jan]Cow Lineup*

bzoj3048[Usaco2013 Jan]Cow Lineup

题意：

给你一个序列，你最多可以删去k类数（数列中相同的数字被称为一类数）。求通过删数得到的该序列中的最长完美序列（满足所有的数字相等的连续子序列被叫做完美序列）。序列大小≤100000

题解：

先离散化，然后维护一个单调队列，如果当前类数小于等于k+1就比较答案，否则左端点++。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 100010
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch=getchar(); int f=1,x=0;
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
12     return f*x;
13 }
14 struct ls{int id,v;}; ls lss[maxn]; int tot,v[maxn],n,k,l,r,cnt[maxn],mx,kinds;
15 bool cmp(ls a,ls b){return a.v<b.v;}
16 int main(){
17     n=read(); k=read(); inc(i,1,n)lss[i]=(ls){i,read()}; sort(lss+1,lss+n+1,cmp);
18     inc(i,1,n){if(i==1||lss[i].v!=lss[i-1].v)tot++; v[lss[i].id]=tot;}
19     l=1; r=1; kinds=0;
20     while(1){
21         while(r<=n&&kinds<=k+1){
22             cnt[v[r]]++; if(cnt[v[r]]==1)kinds++; mx=max(mx,cnt[v[r]]); r++;
23         }
24         if(r==n+1)break;
25         while(kinds>k+1){
26             cnt[v[l]]--; if(!cnt[v[l]])kinds--; l++;
27         }
28     }
29     printf("%d",mx); return 0;
30 }

20160814