[USACO13JAN]牛的阵容Cow Lineup

题目

luogu3069

思路

一道被恶意评分的题目(最多只有绿啊,怎么就蓝了?)。
这题用离散化,尺取法。枚举r就好了。
为什么??
先看看这题
再回来看本题,有没有什么想法?
在一个区间中,一共有<=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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int n,a[maxn],k,b[maxn],c[maxn];
//a,b数组用于离散化,c数组表示当前这种颜色有几个
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
//前面为离散化,复杂度为o(nlogn)
int l=1,r=0,now=0,ans=0;
//l,r不解释,now为当前区间有几种颜色
while(r<=n){
r++;//等同于for(int r=1;r<=n;r++)
if(!c[a[r]])now++; c[a[r]]++;//当前的颜色没有出现过,now++。
while(l<=n&&now>k+1){//直到找到符合的区间
c[a[l]]--; if(!c[a[l]])now--;
l++;//l不用回到之前,为什么呢?
//因为尺取法是在有单调性的前提才用的。
//什么单调性呢?自己想去
}
ans=max(ans,c[a[r]]);//记录/更新答案
}
printf("%d\n",ans);
return 0;
}

就这样,又水了一题,谢谢!!